P7713 「EZEC-10」打分题解

Shunpower · 2021-07-12 11:46:28 · 题解

题目传送门

可能更好的阅读体验

思路

很简单的贪心，我们可以把打分的情况分为三种讨论。

显然，如果要使得答案尽量大，就尽量把除最小得分以外的分数都加成最大的分数。我们可以假设要把除最小值、最大值以外的分数都变成最大分需要加 sum 分，这样就可以举出三种情况：

1.sum=m，刚好可以把除了最大值与最小值以外的分数都变成最大的分数，此时若最大分数为 maxn，答案则是 maxn(n-2)。

2.sum>m，可以保证有至少一种加分办法不改变最大值与最小值。若除最大值最小值以外分数的和为 cnt，答案则是 cnt+m。

3.sum<m，可以先把除了最小值最大值以外的分数都先变成最大值，此时 m 还剩下 m-sum 分可以加。可以把除最小值以外的分数再加上 \frac{m-sum}{n-1} 分，如果还有余数 t，就先把新的序列排序，然后把区间 [2,1+t] （也可以写作 [2,2+t)）中的每个 a_i 都增加 1。

代码

2.1：处理前的准备

cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>a[i];
}
sort(a+1,a+n+1);//排序后，a[1]是最小分数，a[n]是最大分数
for(int i=2;i<=n-1;i++){
    sum+=(a[n]-a[i]);//求出要把所有除了最大和最小分数的分数变成最大分数需要加多少分，即要加多少次
    cnt+=a[i];//求出除最大分数和最小分数的总和
}

我使用了较慢的排序函数来排除最小分数和最大分数，当然可以使用更快的 O(n) 的循环找最大和最小分数。

2.2：第一种情况的处理

if(sum==m){
    cout<<a[n]*(n-2)<<endl;
    return 0;
}

当 sum=m 时，答案就是最大的分数与 (n-2) 的积。

2.3：第二种情况的处理

else if(sum>m){
    cout<<cnt+m<<endl;
    return 0;
}

当 sum>m 时，保证存在至少一种办法可以使得最大分数与最小分数不改变，所以这里可以直接输出 (cnt+m)。

2.4：第三种情况的处理

else{
    for(int i=2;i<=n-1;i++){
        a[i]=a[n];//先把所有除了最小最大分数以外的分数都变成最大分数
    }
    m-=sum;//算出m还剩下多少可以用
    for(int i=2;i<=n;i++){
        a[i]+=m/(n-1);//先把m平摊分给除了最小分数以外的分数
    }
    for(int i=2;i<=1+m%(n-1);i++){
        a[i]++;//如果还有剩的，就把区间[2,1+m%(n-1)]中的a[i]都加一分。
    }
    sort(a+1,a+n+1);//再次排序
    for(int i=2;i<=n-1;i++){
        ans+=a[i];//再次求和
    }
    cout<<ans<<endl;
    return 0;//好习惯
}

当 sum<m 时，先把除了最小最大分数以外的分数都变成最大分数，然后把剩余的 m 先平摊，如果还有剩的，就依次加一，直到最后剩余的这部分也用完。

AC Code

AC记录

P7713 「EZEC-10」打分 题解

思路

代码