题目描述

有一个长度为 n 的数组（n是10的倍数），每个数ai都是区间[0,9]中的整数。
小明发现数组里每种数出现的次数不太平均，而更改第i个数的价为 bi,他想更改若干个数的值使得这10种数出现的次数相等（都于 n/10),请问代价和最少为多少。

输入格式

输入的第一行包含一个正整数 n。
接下来 n 行，第 i 行包含两个整数 ai,bi,用一个空格分隔。

输出格式

输出一行包含一个正整数表示答案。

数据范围

对于20%的评测用例，

n≤1000；

对于所有评测用例，

n≤105，0<bi≤2×105。

输入样例

10
1 1
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9
4 10

输出样例

27

算法 I don`t know. But Ac了

思想:只考虑个数大于n/10,并且在[0,9]区间以内的数。(劫富济贫)

代码奉上！！！

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int used[2*N];
struct node
{
  unsigned long long data;//试过了int过不了,所以直接开最大了
  unsigned long long w;
} a[N];
bool cmp(node a,node b)
{
  if(a.data!=b.data)return a.data<b.data;//先要有序再要代价
  return a.w<b.w;
}
int main()
{
  scanf("%d",&n);
  for(int i=1; i<=n; i++)
    scanf("%d%d",&a[i].data,&a[i].w),used[a[i].data]++;//压时间效率,实际没作用
  sort(a+1,a+n+1,cmp);//cmp懂得都懂会的都会
  unsigned long long ans=0;//答案也得定义一个大的，不然会爆的
  for(int i=1; i<=n; i++)
  {
    if(used[a[i].data]>n/10)
      used[a[i].data]--,ans+=a[i].w;//劫富济贫过程，每次变化代价加,个数减
  }
  printf("%lld",ans);//用printf输出得用%lld
  return 0;
}