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

· · 题解

如果一个人想要拿第一，不用说，他最后一轮的得分必须是 n。

对于之前累积的分数不如这个人高的来说，他们最后一轮怎么样也比不过这个人，因为他们最后一轮的得分比 n 低。

所以要考虑的就是之前累积的分数比这个人高的那些人，假设他们有 x 名，那么最优情况就是他们都得了后 x 名，即他们这一轮的得分是 1 \sim x。

接下来是怎么分配的问题，通过贪心得出：累积分数最高的这一轮得 1 分，第二高的得 2 分…… 直到这个人为止，这样可以使得那些人在这一轮得分后的分数最大值最小。

最后比较这个人，和那些之前累积分数比他高的人经过刚刚的加分后的分数，如果这个人的最终分数都不比那些人小的话，就可能会赢（刚刚就是一种情况）。

以上是针对一个人的情况的基本思路，写成代码肯定是要加一些排序的处理，最坏复杂度 \mathcal O (n \log n)。

再看如何把一个人的情况拓展到全部人，因为刚刚已经得出，那些原来分数比这个人小的是没有什么用的，所以把这些人也算到 c 数组里面是没有关系的；而原来分数比这个人大的，还是分数最高的得 1 分，第二高的得 2 分……，所以对每个人来说，这些人最后一轮的分数也不会改变。对于每个人来说，他的最优得分都是分数{} + n，所以只要把分数{} + n 和 c 数组的最大值比较即可。复杂度 \mathcal O (n \log n)。

#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,b[300001],c[300001],mx=0,ans=0;
void init(){//读入
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
}
int main(){
    init();//读入
    sort(b+1,b+n+1);//b数组排序
    for(int i=1;i<=n;i++)
        c[i]=b[i]+n-i+1;//加分计算（最大值最小化，贪心）
    for(int i=1;i<=n;i++)
        if(mx<c[i])mx=c[i];//mx为c数组中的最大值
    for(int i=n;i>=1;i--)
        if(b[i]+n>=mx)//与c数组中的最大值mx比较
            ans++;
        else//发现如果得分较高的没希望得第一，得分比他低的更没希望，因为b数组也排过序，所以发现一个人没希望得第一了，就可以退出
            break;
    printf("%d",ans);
    return 0;
}