3089546_ac_1452ms_5628k.java

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

import java.util.*;

public class Main 
{
    Scanner cin  = new Scanner (System.in);
    
	static class part
    {
		int t1, t2, less;
    };

    public static void main(String [] args)
    {
        new Main().solve();
    }
    
    private void solve()
    {
		int i, j, n;

		while(true)
		{
			n = cin.nextInt();
			if(n == 0)
			{
				break;
			}

			part [] p = new part[n];

			for(i = 0; i < n; i++)
			{
				p[i] = new part();
				p[i].t1 = cin.nextInt();
				p[i].t2 = cin.nextInt();
				p[i].less = (p[i].t1 < p[i].t2) ? 0 : 1;
			}
			Arrays.sort(p,new Comparator (){
				public int compare(Object a,Object b)
				{
					part p1 = (part)a;
					part p2 = (part)b;

					if(p1.less == p2.less)
					{
						if(p1.less == 0)
						{
							return p1.t1 - p2.t1;
						}
						else
						{
							return p2.t2 - p1.t2;
						}
					}
					else
					{
						return p1.less-p2.less;
					}
				}
			});
			int tot = 0;
			for(i = 0; i < n; i++)
			{
				tot += p[i].t1+p[i].t2;
				for(j = i+1; j < n; j++)
				{
					if(p[i].t2 > p[j].t1)
					{
						p[i].t2 -= p[j].t1;
						p[j].t1 = 0;
					}
					else
					{
						p[j].t1 -= p[i].t2;
						break;
					}
				}
			}
			System.out.println(tot);
		}
    }
}