AcWing 5395. 平均——小小贪心,拿下~~
原题链接
中等
//如果不去证明贪心,本题是一道很简单的贪心题目
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n;
int cnt[11];
LL ans;
struct Query
{
int a, b;
bool operator < (const Query &W) const
{
return b < W.b;
}
}q[N];
int main()
{
cin >> n;
int num = n / 10;//每一个数应该出现的数量
for(int i = 0; i < n; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
q[i] = {a, b};
cnt[q[i].a] ++;
}
sort(q, q + n);
for(int i = 0; i < n; i ++)
{
if(cnt[q[i].a] > num)
{
ans += (LL)q[i].b;
cnt[q[i].a] --;
}
}
cout << ans << endl;
return 0;
}