3078600_ce.java

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

import java.util.*;

public class Main
{
	int max;
	int [] shop = new int [1001000];
	int [] cust = new int [1001000];
	Scanner cin = new Scanner (System.in);

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

		while(true)
		{
			tmp = cin.next();
			if(tmp.compareTo("-1")==0)
			{
				break;
			}
			amout = parse(tmp);
			input(cust);
			int m1 = max;
			inpit(shop);
			int m2 = max;
			int ans = 100000000;
			for(int i = 0; i <= m1 && i + amout <= m2; i++)
			{
				if(cust[i]+shop[i+amout] < ans)
				{
					ans = cust[i]+shop[i+amout];
				}
			}
			if(ans==100000000)
			{
				System.out.println("The payment is impossible.");
			}
			else
			{
				System.out.println(ans+" tenders must be exchanged.");
			}
		}
	}

	private int parse(String tmp)
	{
		int i, a, b;

		i = tmp.indexOf('.');
		if(i < 0)
		{
			return Integer.parseInt(tmp)*100;
		}
		a = Integer.parseInt(tmp.substring(0,i));
		b = Integer.parseInt(tmp.substring(i+1));
		a *= 100;
		if(tmp.length()==i+2)
		{
			b *= 10;
		}
		return a + b;
	}

	private void input(int []array)
	{
		max = 0;
		String tmp;
		int i;
		int acc, cnt;

		Arrays.Fill(array,100000000);
		while(true)
		{
			tmp = cin.next();
			acc = parse(tmp);
			tmp = cin.next();
			cnt = Integer.parseInt(tmp.substring(0,tmp.length()-1));
			while(cnt > 0)
			{
				cnt--;
				for(i = max; i >= 0; i--)
				{
					if(array[i]!=100000000)
					{
						if(array[i+acc] < array[i]+1)
						{
							array[i+acc] = array[i]+1;
							if(i+acc > max)
							{
								max = i+acc;
							}
						}
					}
				}
			}
		}
	}
}