POJ--Lost Cows (线段树)
2024-09-04 19:47:32
题目:http://poj.org/problem?id=2182 http://acm.hdu.edu.cn/showproblem.php?pid=2711
题意:有N头牛,编号为1--N。 乱序排成一列,已知每头牛前面有多少头牛比它的编号小(从第二头牛开始)。
现在需要求这个序列中从前到后,每一头牛的编号。
思路:因为有N头牛,编号为1--N,最后一头牛如果前面有K头牛比它小,那么可以知道最后这头牛的编号为K+1.
当最后一头牛编号为K+1确定以后,再来看倒数第二头牛,如果这头牛前面有K1头牛比它小,那么这头牛的编号
必然是剩下N-1头牛中第(K1+1)大的。然后以此类推。。。。
最开始的线段树为:
最后一头牛前面有0个比它小,那么这是找第(0+1)大的数。为左下角的(1,1)即1.
倒数第二头牛前面有1个比它小,那么这头牛是剩下所有牛中第(1+1)大的,为(3,3)即3
倒数第三头牛前面有2个比它大,那么这头牛是剩下所有牛中第(2+1)大的,为(5,5)即5.
代码:
#include<cstdio>#include<cstring>#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;const int maxn=8010;int n,arr[maxn],sum[maxn<<2];int num[maxn];void build(int l,int r,int rt){sum[rt]=r-l+1;if(l==r) return;int m=(l+r)>>1;build(lson);build(rson);}int query(int p,int l,int r,int rt){sum[rt]--;if(l==r) return l;int m=(l+r)>>1;if(p<=sum[rt<<1]) return query(p,lson);else return query(p-sum[rt<<1],rson);}int main(){while (~scanf("%d",&n)){build(1,n,1);for(int i=2;i<=n;i++) scanf("%d",&arr[i]);arr[1]=0;for(int i=n;i>0;i--)num[i]=query(arr[i]+1,1,n,1);for(int i=1;i<=n;i++)printf("%d\n",num[i]);}return 0;}
最新文章
- 《Javascript高级程序设计》读书笔记(1-3章)
- Java 之 数据库编程(JDBC)
- WS调用的时候报错
- Maven排除项目中同名不同版本的jar
- Grand Central Dispatch (GCD)
- JQuery LazyLoad实现图片延迟加载-探究
- return x>;y?x:y ?:啥意思?
- 互联网“剁手”新方向,VR全景购物忙——全景智慧城市常诚
- JavaScript(jquery)实现二级菜单联动
- 数据库原理 - 序列5 - 事务是如何实现的? - Undo Log解析
- 扒一扒EOS的前世今生
- npx
- C++获取工程路径、exe路径
- ContentControl as CC和ContentPresenter as CP的使用
- 【转载】Hibernate之hbm.xml集合映射的使用(Set集合映射,list集合映射,Map集合映射)
- groupby elasticsearch
- vue如何实现代码打包分离(按需加载)
- 在Windows下编译Emacs
- php-fpm配置文件,指定session保存目录
- 20181029NOIP模拟赛T3