3396168_ac_4266ms_12320k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

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

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

		public int compareTo(Cow that)
		{
			return that.score - this.score;
		}
	}

	class What implements Comparable <What>
	{
		int aid;
		int id;

		public What(int aid, int id)
		{
			this.aid = aid;
			this.id = id;
		}

		public int compareTo(What that)
		{
			if (this.aid == that.aid)
			{
				return this.id - that.id;
			}
			else
			{
				return this.aid - that.aid;
			}
		}
	}

	public static void main(String [] args)
	{
		new Main().run();
	}

	private void run()
	{
		Scanner in = new Scanner (System.in);
		int n, c, f;
		int from, to;

		n = in.nextInt();
		c = in.nextInt();
		f = in.nextInt();
		Cow [] cow = new Cow [c];
		for (int i = 0; i < c; i++)
		{
			cow[i] = new Cow(in.nextInt(), in.nextInt());
		}
		Arrays.sort(cow);
		from = n >> 1;
		to = c - from;
		TreeSet <What> upper = new TreeSet <What> ();
		TreeSet <What> lower = new TreeSet <What> ();

		upper.clear();
		lower.clear();
		
		int suma, sumb, cnt;

		suma = sumb = cnt = 0;

		for (int i = 0; i < from; i++)
		{
			upper.add(new What(cow[i].aid, i));
			suma += cow[i].aid;
		}
		for (int i = from + 1; i < c; i++)
		{
			lower.add(new What(cow[i].aid, i));
		}

		What what;
		boolean [] using = new boolean [c];

		for (Iterator it = lower.iterator(); cnt < from; cnt++)
		{
			what = (What)(it.next());
			sumb += what.aid;
			using[what.id] = true;
		}

		if (suma + sumb + cow[from].aid <= f)
		{
			System.out.println(cow[from].score);
			return ;
		}

		int ans = -1;
		

		for (int i = from + 1; i < to; i++)
		{
			what = upper.last();
			if (cow[i-1].aid >= what.aid)
			{
				continue;
			}
			suma -= what.aid;
			suma += cow[i-1].aid;
			upper.remove(what);
			upper.add(new What(cow[i-1].aid, i));

			lower.remove(new What(cow[i].aid, i));
			if (using[i])
			{
				sumb -= cow[i].aid;
				using[i] = false;
				cnt = 0;
				for (Iterator it = lower.iterator(); cnt < from; cnt++)
				{
					what = (What)it.next();
					if (!using[what.id])
					{
						sumb += what.aid;
						using[what.id] = true;
						break;
					}
				}
			}
			if (suma + sumb + cow[i].aid <= f)
			{
				ans = cow[i].score;
				break;
			}
		}
		System.out.println(ans);
	}
}