题解 P2777 【[AHOI2016初中组]自行车比赛】

· · 题解

题目：luogu P2777

题目大意：有n个人1~i，已有得分ai，本轮发放每人1~n分，不重复，问有几人可能夺冠。

读题后，我们可以很快得到贪心策略：

若i要胜出，则其他人分数要小于他的分数，所以我们把其他人排序，最大的+1，次大的+2，以此类推。最后如果他的分数+n是最大的，则可能成为冠军。

为什么呢？如果j比i高分，j与k交换本轮得分使j所得分更少，则k将得到更大的得分，按我们之前的策略，k之前一定比j高分，则k与j交换本轮得分后分数一定大于i。

但是我们每次都做O(nlogn)的check的话，好像会T。。。于是我们可以先排序，再每次O(n)check排名为i的人。

于是我们神奇的发现：如果一个低分的人可能得冠，比他高分的人也可以。

So？通过这一点我们想到了排序后从大往小check排名为i的人，看有几个能成为冠军，这样还是O(n^2)，还是会T。。。

突然灵光一闪，这里的有序性使我们可以二分答案！

方法出来了！先O(nlogn)排序，然后二分答案log(n)次，每次O(n)check，总的时间复杂度还是O(nlogn)。

贴上代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int ans,a[300010],n,i,l,r,mid,p,j;
inline bool check(int x)
{
    p=a[x]+n;            //如果x要夺冠，先给他最高分
    for(i=1,j=n-1;i<=n;i++)
    {
        if(i==x)continue;     //是自己则跳过
        if(a[i]+j>p)return 0; //最优情况下有更高则不能夺冠
        j--;                  //后面的人得分减一
    }
    return 1;                     //最优情况下没人能比自己高分则可能夺冠
}
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    l=1;r=n;
    while(l<r)
    {
        mid=l+r>>1;
        if(check(mid))
            r=mid；//如果能夺冠，则压缩区间至l~mid
        else l=mid+1;  //如果mid不能，则压缩区间至mid+1~r
    }                      //这样r一定是答案
    printf("%d",n-r+1);
    return 0;
}

写得丑，请见谅。