自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 21:41:30，当前版本为作者最后更新于2016-09-05 22:18:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

如果一个人想要拿第一，不用说，他最后一轮的得分必须是 $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;
}