3080422_tle.java

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

import java.util.*;

public class Main
{
	static final int inf = 2100000000;

	static class part
	{
		String type, name;
		int price, quality;
		int id;
	}

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

	private void solve()
	{
		int cas, ID;
		int n, b;
		Scanner cin = new Scanner (System.in);

		cas = cin.nextInt();
		while(cas > 0)
		{
			cas--;ID = 0;
			n = cin.nextInt();
			b = cin.nextInt();
			part [] com = new part[n];
			int [] q = new int [n];
			int [] pos = new int [n+1];
			for(int i = 0; i < n; i++)
			{
				com[i] = new part();
				com[i].type = cin.next();
				com[i].name = cin.next();
				com[i].price = cin.nextInt();
				q[i] = com[i].quality = cin.nextInt();
			}
			for(int i = 0; i < n; i++)
			{
				int j = i;
				while(j < n && com[j].type.compareTo(com[i].type)==0)
				{
					com[j].id = ID;
				}
				i = j-1;
				ID++;
			}
			for(int i = n-1; i >= 0; i--)
			{
				pos[com[i].id] = i;
			}
			pos[ID] = n;
			int min, bb, ans;
			boolean fail;
			ans = -1;
			for(int i = 0; i < n; i++)
			{
				bb = 0;fail = false;
				for(int j = 0; j < ID; j++)
				{
					min = inf;
					for(int k = pos[j]; k < pos[j+1]; k++)
					{
						if(com[k].quality >= q[i])
						{
							if(com[k].price < min)
							{
								min = com[k].price;
							}
						}
					}
					if(min == inf || bb + min > b)
					{
						fail = true;
						break;
					}
					else
					{
						bb += min;
					}
				}
				if(!fail && q[i] > ans)
				{
					ans = q[i];
				}
			}
			System.out.println(ans);
		}
	}
}