Lost Cows

POJ

题意:\(n(n<=8000)\)头牛的身高各不相同,且在\([1,n]\)之间,已知第\(i(i>=2)\)头牛前面有\(a_i\)头牛比它矮,求每头牛的身高.

分析:倒序来考虑.第\(n\)头牛前面有\(a_n\)头牛比它矮,则\(h_n=a_n+1\).第\(n-1\)头牛前面有\(a_{n-1}\)头牛比它矮,如果\(a_{n-1}<a_n\),则\(h[n]=a_{n-1}+1\),否则\(h[n]=a_{n-1}+2\)(因为它后面那头牛也比它矮).所以可以发现,我们倒序来考虑的话,第\(i\)头牛的身高就是在剩下的数字中第\(a_i+1\)大的数,这个可以用一个数据结构来维护.

树状数组.初始化\(b\)序列全部为1,表示每个数字都还未被取,然后树状数组维护该序列的前缀和,对于每次查询就是序列中第\(a_i+1\)个为1的数位,因为我们已经维护了序列的前缀和,所以这个显然可以二分查找.该位置就是第\(i\)头牛的身高,然后在更新树状数组.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=8005;
int n,a[N],b[N],c[N],h[N],bj[N];
inline int lowbit(int x){return x&-x;}
inline void add(int x,int v){for(;x<=n;x+=lowbit(x))c[x]+=v;}
inline int ask(int x){int cnt=0;for(;x;x-=lowbit(x))cnt+=c[x];return cnt;}
int main(){
    n=read();for(int i=2;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)b[i]=1,add(i,1);
    for(int i=n;i>=2;--i){
        int l=1,r=n,ans=0;
        while(l<=r){//二分查找到第ai+1个数字为1的位置
            int mid=(l+r)>>1;
            if(ask(mid)>=a[i]+1)ans=mid,r=mid-1;
            else l=mid+1;
        }
        h[i]=ans;b[ans]=0;add(ans,-1);bj[ans]=1;//更新答案和树状数组
    }
    for(int i=1;i<=n;++i)if(!bj[i])h[1]=i;//最后剩下的就是第一头牛的身高
    for(int i=1;i<=n;++i)printf("%d\n",h[i]);
    return 0;
}

Lost Cows

原文：https://www.cnblogs.com/PPXppx/p/11688079.html