poj2182 Lost cows

题目链接:https://vjudge.net/problem/POJ-2182

题意:n头牛,身高为1到n的一个排列。已知每头牛前面比它矮的个数,求每头牛的身高

这题和习题里的poj2828基本一样。倒着考虑,如果最后一头牛前面有k1个比它矮,那么它的身高就是k1+1。倒数第二头如果有k2个比它矮,那么它的身高是一个数(不等于k1+1),且满足:比它小的而且没出现过的数的个数为k2。等价于需要维护一个01序列,要求支持把1变成0的操作(是否出现过);求出一个数,它的前缀和为某个值(有多少个数比当前的小)。单点修改和求前缀和可以用树状数组,快速求出这个数的位置用二分即可

#include<cstdio>
using namespace std;

const int N=8000+10;
int c[N],a[N],res[N],b[N],n,i,j,k,l,r;

void add(int x,int y){
	for (int i=x;i<=n;i+=i&(-i)) c[i]+=y;
}
int ask(int x){
	int res=0;
	for (int i=x;i>0;i-=i&(-i)) res+=c[i];
	return res;
}

int main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++) add(i,1);
	for (i=2;i<=n;i++) scanf("%d",&a[i]);
	for (i=n;i>=2;i--){
	  l=0; r=n;
	  while (r-l>1){
	  	int m=(l+r)/2; 
	  	if (ask(m)<a[i]+1) l=m; else r=m;  //*
	  }
	  res[i]=r; b[r]=1; add(r,-1);
	}
	for (i=1;i<=n;i++) if (!b[i]) res[1]=i;
	for (i=1;i<=n;i++) printf("%d\n",res[i]);
	return 0;
}

  

上一篇:C++堆指针栈指针


下一篇:[loj3046]语言