POJ2010.java

package pojproj;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class POJ2010list {
	static Scanner sc = new Scanner(System.in);
	static int n, c, f;
	static ArrayList<Pair> pairList;
	static ArrayList<Pair> answerList;
	static Comparator<Pair> aidComparator = new AidComparator();
	static Comparator<Pair> scoreComparator = new ScoreComparator();

	public static void main(String[] args) {
		read();
		answerList = new ArrayList<Pair>();
		solve();
	}

	public static void solve() {
		int score = 0;
		for (int i = 0; i < n; i++) {
			Pair pair;
			Comparator<Pair> comparator = scoreComparator;
			if (i > Math.floor(n / 2)) {
				// コスト小さい順に解く
				comparator = aidComparator;
			}
			Collections.sort(pairList, comparator);
			pair = pairList.get(0);
			score += pair.aid;
			answerList.add(pair);
			pairList.remove(0);
		}
		check(score);
	}

	static void check(int score) {
		if (score > f) {
			again(score);
			return;
		}
		outputAnswer();
	}

	static void outputAnswer() {
		Collections.sort(answerList, scoreComparator);
		System.out.println(answerList.get((int) Math.floor(n / 2)).score);
	}

	static void again(int score) {
		Collections.sort(answerList, aidComparator);
		score -= answerList.get(answerList.size() - 1).score;
		answerList.remove(answerList.size() - 1);
		addHigherScore(score);
	}

	static void addHigherScore(int score) {
		if (pairList.size() == 0) {
			System.out.println(-1);
			return;
		}
		Collections.sort(pairList, scoreComparator);
		score += pairList.get(0).score;
		answerList.add(pairList.get(0));
		pairList.remove(0);
		check(score);
	}

	public static void read() {
		n = sc.nextInt();
		c = sc.nextInt();
		f = sc.nextInt();
		pairList = new ArrayList<Pair>();

		for (int i = 0; i < c; i++) {
			int s = sc.nextInt();
			int a = sc.nextInt();
			Pair pair = new Pair(s, a);
			pairList.add(pair);
		}
	}

	static class ScoreComparator implements Comparator<Pair> {

		@Override
		public int compare(Pair o1, Pair o2) {
			Pair pair1 = o1;
			Pair pair2 = o2;
			if (pair1.score < pair2.score) {
				return 1;
			} else if (pair1.score > pair2.score) {
				return -1;
			} else {
				return 0;
			}
		}
	}

	static class AidComparator implements Comparator<Pair> {

		@Override
		public int compare(Pair o1, Pair o2) {
			Pair pair1 = o1;
			Pair pair2 = o2;
			if (pair1.aid > pair2.aid) {
				return 1;
			} else if (pair1.aid < pair2.aid) {
				return -1;
			} else {
				return 0;
			}
		}
	}

	static class Pair {
		private int score;
		private int aid;

		public Pair(int s, int a) {
			this.score = s;
			this.aid = a;
		}
	}
}

ver1.1(TLE)

package pojproj;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class POJ2010list {
	static Scanner sc = new Scanner(System.in);
	static int n, c, f;
	static ArrayList<Pair> pairList;
	static ArrayList<Pair> answerList;
	static Comparator<Pair> aidComparator = new AidComparator();
	static Comparator<Pair> scoreComparator = new ScoreComparator();
	static Comparator<Pair> currentComparator;

	public static void main(String[] args) {
		read();
		answerList = new ArrayList<Pair>();
		solve();
	}

	public static void solve() {
		int aid = 0;
		Collections.sort(pairList, scoreComparator);
		currentComparator = scoreComparator;
		for (int i = 0; i < n; i++) {
			if (i == Math.floor(n / 2) + 1) {
				// コスト小さい順に解く
				Collections.sort(pairList, aidComparator);
				currentComparator = aidComparator;
			}
			Pair pair;
			pair = pairList.get(0);
			aid += pair.aid;
			answerList.add(pair);
			pairList.remove(0);

		}
		check(aid);
	}

	static void check(int aid) {
		if (aid > f) {
			again(aid);
			return;
		}
		outputAnswer();
	}

	static void outputAnswer() {
		Collections.sort(answerList, scoreComparator);
		System.out.println(answerList.get((int) Math.floor(n / 2)).score);
	}

	static void again(int aid) {
		Collections.sort(answerList, aidComparator);
//		System.out.println("捨てるスコアは"+answerList.get(answerList.size()-1).score);
		aid -= answerList.get(answerList.size() - 1).aid;
		answerList.remove(answerList.size() - 1);
		addHigherScore(aid);
	}

	static void addHigherScore(int aid) {
		if (pairList.size() == 0) {
			System.out.println(-1);
			return;
		}
		Collections.sort(pairList, scoreComparator);
		aid += pairList.get(0).aid;
//		System.out.println("追加するスコアは"+pairList.get(0).score);
		answerList.add(pairList.get(0));
		pairList.remove(0);
		check(aid);
	}

	public static void read() {
		n = sc.nextInt();
		c = sc.nextInt();
		f = sc.nextInt();
		pairList = new ArrayList<Pair>();

		for (int i = 0; i < c; i++) {
			int s = sc.nextInt();
			int a = sc.nextInt();
			Pair pair = new Pair(s, a);
			pairList.add(pair);
		}
	}

	static class ScoreComparator implements Comparator<Pair> {

		@Override
		public int compare(Pair o1, Pair o2) {
			Pair pair1 = o1;
			Pair pair2 = o2;
			if (pair1.score < pair2.score) {
				return 1;
			} else if (pair1.score > pair2.score) {
				return -1;
			} else {
				return 0;
			}
		}
	}

	static class AidComparator implements Comparator<Pair> {

		@Override
		public int compare(Pair o1, Pair o2) {
			Pair pair1 = o1;
			Pair pair2 = o2;
			if (pair1.aid > pair2.aid) {
				return 1;
			} else if (pair1.aid < pair2.aid) {
				return -1;
			} else {
				return 0;
			}
		}
	}

	static class Pair {
		private int score;
		private int aid;

		public Pair(int s, int a) {
			this.score = s;
			this.aid = a;
		}
	}
}