原生态旅游网站开发需求分析百度实名认证
原题路径
题目思路 : 思路很简单,肯定是贪心做法,要使总代价最小,需用那些出现次数比avg多的数来替换那些没有出现或者是出现次数少于avg的数, 所以我们存当前数每次出现的代价是多少 ,枚举每一个 0 - 9 之间的数 ,如果当前数出现的次数多于avg,那么说明需要减少,每次用最小的代价替换即可
由于我们并不知道替换的数是哪一个,但由于题目中说明了每个数都会出现 n / 10 次,所以证明一旦多出来的数必定会替换为另一个数,故我们只需要从小到大替换,将 avg 个当前数中价值最大的保存即可。#include <iostream> #include <cstring> #include <algorithm>using namespace std;const int N = 1e5 + 10;int n; int a[N] , b[N]; vector<int> h[N];int main() {cin >> n;for(int i = 1 ; i <= n ; i ++){int a , b;cin >> a >> b;h[a].push_back(b);}int avg = n / 10;long long res = 0;for(int i = 0 ; i < 10 ; i ++){int x = h[i].size();if(x > avg){sort(h[i].begin() , h[i].end());for(int j = 0 ; j < h[i].size() - avg ; j ++){res += h[i][j];}}}printf("%lld" , res);return 0; }