题解 P2777 【[AHOI2016初中组]自行车比赛】
小粉兔
·
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
#include
#include
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 for(int i=n;i>=1;i--) if(b[i]+n>=mx)//与c数组中的最大值mx比较 ans++; else//发现如果得分较高的没希望得第一，得分比他低的更没希望，因为b数组也排过序，所以发现一个人没希望得第一了，就可以退出 break; printf("%d",ans); return 0; }