编写题解 2109: 增添战力 贪心算法

解题思路: 所需人数最小的优先放入战力高的

参考代码:

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class T2109 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int pi[] = new int[n];
		double[][] num = new double[2][2];// 两个城池 0存放所需人数 1存放城池战力和
		for (int i = 0; i < num.length; i++) {
			num[i][0] = scanner.nextInt();
		}
		for (int i = 0; i < pi.length; i++) {
			pi[i] = scanner.nextInt();
		}
		Arrays.sort(pi);
		Arrays.sort(num, new Comparator<double[]>() { // 根据人数和战力差值排列二维数组
					public int compare(double[] o1, double[] o2) {
						return (o1[0] - o1[1]) - (o2[0] - o2[1]) > 0 ? 1 : -1;
					}
				});
		int j = n - 1;// 从战力高开始
		int count = 0;
		for (int i = 0; i < 2; i++) {
			for (; j >= 0 && count < num[i][0]; j--, count++) {
				num[i][1] += pi[j];
			}
			count = 0;
		}
		System.out.printf("%.6f", (num[0][1] / num[0][0])
				+ (num[1][1] / num[1][0]));
	}

}