排序,计算n/10,然后从小到大将次数多于n/10的代价求和。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 5;
int cnt_num[10];
typedef long long ll;
PII a[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++)
{
cin >> a[i].first >> a[i].second;
cnt_num[a[i].first] ++;
}
sort(a, a + n);
int cnt = n / 10;
ll ans = 0;
for (int i = 0; i < n; i ++)
{
if (cnt_num[a[i].first] > cnt)
{
ans += (ll)a[i].second;
cnt_num[a[i].first] --;
}
else continue;
}
cout << ans << endl;
return 0;
}