原题链接
考察:树状数组+二分
完全没想到,fw本f
思路:
这道题实际有点像逆康拓展开.对于某个位置i,在它前面的数有a[i]个.第一头牛是无法确定身高的,但是如果我们从后往前考虑就可以用排除法确定身高.
对于最后一头牛,比它矮的有a[n]个,说明它是1~n中,第a[i]+1个数.我们考虑第n-1头牛的时候,排除掉h[n] (h表示第i头牛身高).然后再求剩余数的第a[n-1]+1个数.
求某个序列的第k个数.考虑二分.那么怎么快速得到剩余数序列呢?这里又有点类似树状数组的经典题:数星星.以tr[i]表示i是否存在.第k个数代表它前面有k-1个1.而前缀和数组又是一定有单调性的(不考虑负数)
时间复杂度:O(nlog2n*log2mid)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N],n,tr[N],h[N];
int lowbit(int i)
{
return i&-i;
}
void add(int k,int x)
{
for(int i=k;i<=n;i+=lowbit(i)) tr[i]+=x;
}
int ask(int k)
{
int ans = 0;
for(int i=k;i;i-=lowbit(i)) ans+=tr[i];
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) add(i,1);
for(int i=n;i>=1;i--)
{
int l = 1,r = n;
while(l<r)
{
int mid = l+r>>1;
if(ask(mid)>a[i]) r = mid;
else l = mid+1;
}
h[i] = r;
add(h[i],-1);
}
for(int i=1;i<=n;i++) printf("%d\n",h[i]);
return 0;
}
···