POJ 2182【树状数组】

题意：

每头牛有编号，他们乱序排成一排，每头牛只知道前边比自己序号小的有几位。

思路：

递推，最后一只牛的编号是确定的，然后不断进行区间更新，直到找到某个空位前方恰好有n个空位。

这题跟某道排队的题思路是一样的，可以线段树，认为树状数组的解法在时间复杂度上比线段树多了一个logN

因为树状数组只能在logn的复杂度内求解出前n个数字的某些特征，所以需要进行二分不断尝试，直到找到某一个位置前方正好有多少个空位，也就是在二分的过程中使得时间复杂度比线段树要高。线段树直接进行查找就好了，复杂度是logn。

反思：

这道题的WA在二分上，并不是前n个空位中恰好有k个空位就可以安置这头牛，因为有可能这个位置本身就已经有人占据了。所以二分一定要使得两个区间端点会和。

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int tree[];

int tmp[];

int ans[];

int n;

int lowbit(int a)

{

    return a&(-a);

}

int solve(int tar)

{

    int sum=;

    while(tar>)

    {

        sum+=tree[tar];

        tar-=lowbit(tar);

    }

    return sum;

}

int findpos(int tar)

{

    int l=,r=n;

    while(l<r)

    {

        int mid=(l+r)>>;

        if(solve(mid)<tar)

        {

            l=mid+;

        }

        else

        {

            r=mid;

        }

    }

    return l;

}

void change(int tar)

{

    while(tar<=n)

    {

        tree[tar]--;

        tar+=lowbit(tar);

    }

}

int main()

{

    scanf("%d",&n);

    tmp[]=;

    for(int i=;i<=n;i++)

    {

        scanf("%d",&tmp[i]);

    }

    for(int i=;i<=n;i++)

    {

        tree[i]=lowbit(i);

    }

    for(int i=n;i>;i--)

    {

        int tans=findpos(tmp[i]+);

        change(tans);

        ans[i]=tans;

    }

    for(int i=;i<=n;i++)

    {

        printf("%d\n",ans[i]);

    }

    return ;

}

POJ 2182【树状数组】的相关教程结束。