Lost Cows
Description N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow Given this data, tell FJ the exact ordering of the cows. Input * Line 1: A single integer, N * Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows Output * Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on. Sample Input 5 1 2 1 0 Sample Output 2 4 5 3 1 Source |
评测链接:http://poj.org/problem?id=2182
解法:
在网上看的题解,不得不说,又了解了线段树的一种应用方法。
我们可以假想一个1到n的序列x,表示1到n头牛的编号。
第n头牛在序列x中,只有a[n]头牛的编号比它小,那么它在序列中的就排在第a[n]+1位,也即第n头牛的编号为a[n]+1,用d[n]=a[n]+1记录编号。
第n-1头牛对应的编号在序列中就是排在第a[n-1]+1个点所对应的编号(不包括d[n]号点)。
。。。。。。
以样例为例:
x:1 2 3 4 5
a:0 1 2 1 0
第一步:a[n]=0,在序列x中排在第0+1位,所以d[n]=1;
第二步:不算d[n]号点,新x序列为:2 3 4 5
a[n-1]=1,在序列中排在第1+1位,即d[n-1]=3;
。。。。。。
具体做法:用线段树sum[]维护序列x的区间中p【pl,pr】中,有多少个已被确认的点,那么新序列x在区间p中就有pr-pl+1-sum[p]个点。在查找新序列中第i位时,就可以用线段树进行查找。(鄙人词乏,查找过程真不知该咋样叙述,还请看代码上的注解。)
代码:
#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #define maxn (8000+100) using namespace std; //sum 维护线段树,d记录第i头牛的编号,a记录第i头牛前面有多少头牛的编号比他小 int sum[maxn*3],d[maxn],a[maxn]; void init() { freopen("lost_cows.in","r",stdin); freopen("lost_cows.out","w",stdout); } //手写读入输出 inline int getin() { int ans=0; char tmp; do tmp=getchar(); while(!isdigit(tmp)); do ans=(ans<<3)+(ans<<1)+tmp-'0'; while(isdigit(tmp=getchar())); return ans; } //在区间p[pl,pr]中查找新序列中第i个位置的编号。 int get(int p,int pl,int pr,int i) { //查询时对线段树进行维护,在区间p中查询第i位,那么区间 p中势必就会多一个已确认点 sum[p]++; if(pl==pr)return pl;//pl==pr代表以找到新序列中的第i号位置 int m=(pl+pr)>>1,k=p<<1,sumz=m-pl+1-sum[k];//sumz表示p的左区间内有多少个新序列中的点 if(sumz>=i)return get(k,pl,m,i);//若sumz>=i,代表第i号点在p的左区间 return get(k+1,m+1,pr,i-sumz);//sumz<=i,代表第i号点在p的右区间 } void work() { int n=getin(),i; a[1]=0; for(i=2;i<=n;i++)a[i]=getin(); memset(sum,0,sizeof(int)*(n*3)); for(i=n;i>0;i--)d[i]=get(1,1,n,a[i]+1); for(i=1;i<=n;i++)printf("%d\n",d[i]); } int main() { init(); work(); return 0; }