1.题目思路

一道贪心。

显然，修改任意一个数对每种数出现次数的贡献都相等（最多只可能让出现次数变化

1

），所以就是比较朴素的贪心（~~作者一开始甚至有动态规划的念头~~）。所以取代价小的进行修改一定比取代价大的优。

很容易转化成：用结构体存储每个数对应的值、修改代价，并按照修改代价从小到大排序。接着从前往后遍历，如果当前这个数出现的次数大于

\dfrac{n}{10}

（题目中给出），那么就选这个数修改（不必在意其被修改为什么数，最终一定会使所有数出现次数相等，因为题目保证

n

是

10

的倍数），答案累加修改代价，并让当前数出现次数减

1

（最优解下，当前数一定会修改成其他数，否则就浪费了这次操作）。

最终输出答案即可。注意到

b_i

的值域较大，保险起见答案变量记得开

\texttt{long long}

！

2.代码

注：代码仅供参考。

CPP

123456789101112131415161718192021222324252627282930#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;
}

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

文章操作

1.题目思路

2.代码

3.后记

相关推荐

评论

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