POJ_2182 Lost Cows(线段树的简单应用)
2024-08-25 13:11:21
基本思路就是,从后往前读取数字small[i]。在剩余编号集合里(一开始剩余编号集合为全集)查找第small[i]+1个编号,该编号就是对应位置牛的编号。
若直接用数组来做,则每次查找都需要遍历前n个数。而用线段树来做则可以降低为nlogn的复杂度。
事实上感觉可以直接用stl的set来做,直接模拟应该也能不超时得解。
本题主要用来熟悉线段树这个结构。
ac代码如下:
#include<iostream>
#include<cstdio>
#include<cstdio>
using namespace std;
const int maxn=;
int small[maxn],ans[maxn];
struct node{
int lc,rc,len;
};
node tree[maxn*];//这里一开始数组开小了出现了rte
void build(int x,int lc,int rc){
tree[x].lc=lc,tree[x].rc=rc;
tree[x].len=rc-lc+;
if(lc==rc)return ;
build(x*,lc,(lc+rc)/);
build(x*+,(lc+rc)/+,rc);
}
int query(int base,int k){
tree[base].len--;
if(tree[base].lc==tree[base].rc)return tree[base].lc;
if(k<=tree[base*].len){
return query(base*,k);
}
else{
return query(base*+,k-tree[base*].len);
}
}
int main(void){
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&small[i]);
}
small[]=;
build(,,n);
for(int i=n;i>=;i--){
ans[i]=query(,small[i]+);
}
for(int i=;i<=n;i++){
printf("%d\n",ans[i]);
}
return ;
}
最新文章
- oracle返回多个参数
- hibernate反向生成映射文件报错
- glsl计算sprite的亮度饱和度对比度
- 获取不到app.config里面的数据库连接字符串的解决方法
- Thinkphp 缓存微信jssdk相关认证参数
- CANoe 入门 Step by step系列(一)基础应用【转】
- a标签中调用js的几种方法
- [COGS 1065] 绿豆蛙的归宿
- IE9下table th不显示边框解决方法
- 80x86的内存寻址机制
- javase每天内容总结(32期)
- pngencoder图像转换jar
- MHL相关资源链接
- package &#39;yaml-cpp&#39; not found
- hdu3089 Josephus again|快速约瑟夫环
- Android Issue分析方法(用anr来说明)
- Qt 学习之路 2(44):QFileSystemModel
- HDU - 3072 Intelligence System
- mac的vim使用
- Xcode5 如何添加一个Github/Repository 并且Checkout
热门文章
- 转!!Linux 里的 2>;&;1 究竟是什么
- 【非root用户】安装【python,pip,package】
- CF #301 E:Infinite Inversions(逆序数,树状数组)
- js获取浏览器信息及版本(兼容IE)
- Saltstack之SSH简介
- nodejs获取参数的方法
- SIP UserAgent (B2BUA client)——pjsip
- Spark的集群管理器
- 转Hibernate 一对多关联的CRUD__@ManyToOne(cascade=(CascadeType.ALL))
- 利用crontab系统每天定时备份MySQL数据库及删除指定crontab定时任务