蓝桥杯：平均（Java）

问题描述

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

输入格式

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

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

输出格式

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

27

样例说明
只更改第1,2,4,5,7,8个数，需要花费代价1＋2＋4＋5＋7＋8 = 27。

代码实现

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		// 在此输入您的代码...
		int cols = scan.nextInt();// 输入数组个数
		int[][] arr = new int[cols][2];// 将每组数据存入数组
		int[] sum = new int[10];// 统计0到9出现的次数
		int avg = cols / 10;// 每个数的平均出现次数
		int cost = 0;// 最低代价
		for (int i = 0; i < cols; i++) {
			arr[i][0] = scan.nextInt();// 整数
			arr[i][1] = scan.nextInt();// 代价
			sum[arr[i][0]]++;// 计数
		}
		// 对代价进行升序排序:即仅对二维数组第1列进行升序排序
		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				return (int) (o1[1] - o2[1]); // 按第一列升序排序
			}
		});// 需要重写匿名内部类的排序方法

		// 开始计算最低代价：只对超出平均次数的位置进行替换，低于平均次数的情况直接不管
		for (int i = 0; i < cols; i++) {
			if (sum[arr[i][0]] > avg) {
				// 出现次数超出平均次数的情况
				cost += arr[i][1];// 添加代价
				sum[arr[i][0]]--;// 计数减一

			}
		}
		System.out.println(cost);// 打印最低代价
		scan.close();
	}

}