POJ 2010-Moo University - Financial Aid

問題（外部リンク）

2010 -- Moo University - Financial Aid

実装の概要

今回の問題の目的は、予算内でスコアの平均を最大にすることではなく「中央値」を最大にすることです。例えば問題ページにある入力例では30点、20点、5点のいずれを選んだとしても中央値は35であることに変わりはありません。それならば最も金額の少ない5点の牛を選ぶべきです。
一般化すると、合格できる牛の数がnならば中央値より上のグループも下のグループもちょうどそれぞれ(n-1)/2匹となります。そこで、まずは牛をスコア順に並べ、ある牛の点数を中央値であると仮定してその上のグループおよび下のグループの合計金額の最小値を求めます。
ただし、その都度「上のグループ内で金額順にソート」などをすると計算量が多く間に合いません。そこで優先度付きキューを使います。
優先度付きキューでの並びを「金額が高い順」にし、なおかつキューのサイズを常に高々(n-1)/2になるようにすると、常に「（金額的に）最優先で不合格にすべき牛」が先頭に来ます。追加も削除もO(log n)で済むので（O(log c）ではありません）間に合います。
あとはこの優先度付きキューを使いながら計算結果をメモしておくと最後にループを回すだけで答えを求めることができます。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] tmpArray = br.readLine().split(" ");

		int n = Integer.parseInt(tmpArray[0]);
		int c = Integer.parseInt(tmpArray[1]);
		int f = Integer.parseInt(tmpArray[2]);

		Cow[] cows = new Cow[c];

		for(int i = 0; i < c; i++){
			tmpArray = br.readLine().split(" ");

			int score = Integer.parseInt(tmpArray[0]);
			int aid = Integer.parseInt(tmpArray[1]);

			cows[i] = new Cow(score, aid);

		}

		System.out.println(solve(n, f, cows));
	}

	public static int solve(int n, int f, Cow[] cows){
		//スコアの高い順
		Arrays.sort(cows);

		int c = cows.length;
		int half = (n - 1)/2;

		long totalCost[][] = new long[2][c];

		PriorityQueue<Cow> high = new PriorityQueue<Cow>(n, new Comparator<Cow>() {

			//高い順
			@Override
			public int compare(Cow c1, Cow c2) {
				return c2.aid - c1.aid;
			}
		});

		//中央値よりも上の最小合計値の計算
		long tmpTotal = 0;
		for(int i = c - 1 ; i >= 1; i--){
			high.add(cows[i]);
			tmpTotal += cows[i].aid;

			if(high.size() > half){
				Cow tmpCow = high.remove();
				tmpTotal -= tmpCow.aid;
			}

			totalCost[0][i - 1] = tmpTotal;
		}

		PriorityQueue<Cow> low = new PriorityQueue<Cow>(n, new Comparator<Cow>() {

			@Override
			//高い順
			public int compare(Cow c1, Cow c2) {
				return c2.aid - c1.aid;
			}
		});

		//中央値よりも下の最小合計値の計算
		tmpTotal = 0;
		for(int i = 0 ; i < c - 1; i++){
			low.add(cows[i]);
			tmpTotal += cows[i].aid;

			if(low.size() > half){
				Cow tmpCow = low.remove();
				tmpTotal -= tmpCow.aid;
			}

			totalCost[1][i + 1] = tmpTotal;
		}

		//「中央値より上の合計金額」+「中央値より下の合計金額」+「中央値の金額」がf以下ならreturn
		for(int i = c - half - 1; i >= half ; i--){
			if(totalCost[0][i] + totalCost[1][i] + cows[i].aid <= f){
				return cows[i].score;
			}
		}

		return -1;
	}

}

class Cow implements Comparable<Cow>{
	int score;
	int aid;

	public Cow(int score, int aid){
		this.score = score;
		this.aid = aid;
	}

	@Override
	public int compareTo(Cow c) {
		return (this.score - c.score);
	}
}