题意:
n头牛站队,每头牛都有一个属于[1,n]唯一的数字。对于每头牛,现在已知前面多少头牛的数字比他的大,问这n头牛的数字序列。
思路:
和poj2828很相似,都是从后向前计算,建立一颗线段树,节点val值为,这个区间的空位数,然后从后向前更新线段树,也就是说,如果一个节点无法插入当前位置,那么就选择右侧最靠近这个节点的位置
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int nMax = 8010; struct{ int l , r ,num; }node[nMax*3]; int num[nMax] ,ans ,res[nMax]; void build(int l ,int r, int u){ node[u].l = l; node[u].r = r; node[u].num = r - l + 1; if(l == r){ return; } int m = (r + l)>>1; build(l , m , u*2); build(m + 1, r , u*2 + 1); } void update(int p ,int u){ int l = node[u].l; int r = node[u].r; node[u].num -= 1; if(l == r){ ans = r; return; } if(node[2*u].num >= p){ update(p ,u*2); }else{ p -= node[2*u].num; update(p ,u * 2 + 1); } } int main(){ int n , i; while(scanf("%d",&n)!=EOF){ for(i = 2 ;i <= n ;i++){ scanf("%d",&num[i]); num[i] ++; }num[1] = 1; build(1 ,n ,1); for( i = n ; i >= 1; i--){ update(num[i] ,1); res[i] = ans; } for(i = 1; i<= n; i++) printf("%d\n",res[i]); } return 0; }
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1740501
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2763 程序 线段树 LCA 2000MS AC
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://128kj.iteye.com/blog/1746750
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
POJ3468,线段树处理,注意longlongint
此为本人在poj做过的经典题目的代码与一些经典数据结构算法的模板程序,如线段树,拓扑排序等
以每个星星为中心,得到可以罩住它的矩形的左下角的范围,这些范围内的点增加星星亮度,由于落在框上的点不算,框不一定要整数起点,可另左下落在框上算。求亮度和最大的点即可。...每次用线段树更新和求最大值。
POJ 2182 引自余立功《算法训练教程》,线段树的应用
acm code of 20053565 poj onlinejudge 高精度 DP 图论 算法 最大流 最小生成树 线段树