POJ2182 Lost Cows 树状数组，二分

2020-12-13 15:40

阅读：564

标签：clu size while 个数 its i++ 数字 += 表示

题意：给n个奶头身高从1到n，现在奶牛排成一列，给n-1个数字，为第二号奶牛到第n号奶牛前面比它矮的奶牛个数。

求这个序列每个奶牛的身高。

思路：从最后一个奶牛开始判断，因为最后一个奶牛是和前面所有奶牛做比较的，我们可以根据比它矮的奶牛个数确定它的身高，如果前面有3个比它矮那么它身高绝对为4，而继续判断前一个奶头身高时，要把这个奶牛剔除考虑，

所以我们想到可以维护一个长度为n的01序列，为1表示奶牛还在，奶牛从后往前遍历，设比它矮的有k个，每次找奶牛身高，就是找存在的奶牛中k+1的位置，也就是前缀和为k+1的位置,每次可以二分来判断位置，0（1）删除一个奶牛

#includeusing namespace std;

const int maxn=8e3+10;
#define ll long long
int a[maxn];
int c[maxn];
int n;
int ans[maxn];
int ask(int x)
{
    int ans=0;
    for(; x; x-=x&-x)
        ans+=c[x];
    return ans;
}
void add(int x,int y)
{
    for(; xy;
}
int vis[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=2; i)
        scanf("%d",&a[i]);
    for(int i=1; i)
        add(i,1);
    for(int i=n; i>=2; i--)
    {
        int l,r,mid;
        l=1,r=n;
        while(lr)
        {
            mid=(l+r)/2;
            int t=ask(mid);
            if(t>=a[i]+1)
                r=mid-1;
            else
                l=mid+1;
        }
        ans[i]=l;
        vis[l]=1;
        add(l,-1);
    }
    for(int i=1; i)
    {
        if(vis[i]==0)
        {
            ans[1]=i;
            break;
        }
    }
    for(int i=1; i)
        printf("%d\n",ans[i]);
}

POJ2182 Lost Cows 树状数组，二分

标签：clu size while 个数 its i++ 数字 += 表示

原文地址：https://www.cnblogs.com/dongdong25800/p/11613863.html

上一篇：JAVA学生学籍管理系统

下一篇：Delphi 设计模式：《HeadFirst设计模式》Delphi2007代码---组合模式之Menus[转]

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：POJ2182 Lost Cows 树状数组，二分
文章链接：http://soscw.com/essay/35322.html

亲，登录后才可以留言！

POJ2182 Lost Cows 树状数组，二分

评论

热门文章

推荐文章

最新文章

置顶文章