题解：P13878 [蓝桥杯 2023 省 Java/Python A] 平均

· · 题解

1.题目思路

一道贪心。

显然，修改任意一个数对每种数出现次数的贡献都相等（最多只可能让出现次数变化 1），所以就是比较朴素的贪心（作者一开始甚至有动态规划的念头）。所以取代价小的进行修改一定比取代价大的优。

很容易转化成：用结构体存储每个数对应的值、修改代价，并按照修改代价从小到大排序。接着从前往后遍历，如果当前这个数出现的次数大于 \dfrac{n}{10}（题目中给出），那么就选这个数修改（不必在意其被修改为什么数，最终一定会使所有数出现次数相等，因为题目保证 n 是 10 的倍数），答案累加修改代价，并让当前数出现次数减 1（最优解下，当前数一定会修改成其他数，否则就浪费了这次操作）。

最终输出答案即可。注意到 b_i 的值域较大，保险起见答案变量记得开 \texttt{long long}！

2.代码

注：代码仅供参考。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int max_n=1e5+2;
int n,times[11]; //每种数出现的次数
long long ans; //答案（开 long long）
struct node{ //每个数
    int a,b;
} nums[max_n];
bool cmp(node a,node b){
    return a.b<b.b;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&nums[i].a,&nums[i].b);
        times[nums[i].a]++;
    }
    sort(nums+1,nums+n+1,cmp);
    int tot=n/10;
    for(int i=1;i<=n;i++){
        if(times[nums[i].a]>tot){
            ans+=nums[i].b;
            times[nums[i].a]--;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

3.后记

更多内容，请移步至：

  1. \color{red}\texttt{Luogu ryf2011}；
  2. \color{orange}\texttt{cnblogs（博客园） cnblogs2011ryf}。