POJ 2709 Painter ——JAVA实现

JAVA实现POJ2709——稻草人

原题：http://poj.org/problem?id=2709

 

题意：

给出几种颜色需求的ml量，然后最后一个数是灰色需求量，灰色可以由任何三中不同颜色的颜色组成，每个颜料盒有所给出的颜色50ml。

问最少给出几个颜料盒，可以组成所需求颜色

用贪心来解决，先求出满足的普通色所需的最小盒数，然后把剩余颜料从大到小排列，那前三种每个取出1ml组成1ml的灰色(每次取1ml才能达到最优解)。

 

代码：

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	static int Gray = 0;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext())
		{
			int nCase = in.nextInt();
			if(nCase==0)
				break;
			int max = 0;
			Integer[] array = new Integer[nCase];
			for(int i=0;i<nCase;i++)
			{
				array[i]=in.nextInt();
				if(array[i]>max)
					max = array[i];
			}
			Gray = in.nextInt();
			System.out.println(getAns(array,max));
		}

	}
	static int getAns(Integer[] array,int max)
	{
		int count=0;
		count+=max/50;
		if(max%50!=0)
			count++;
		for(int i=0;i<array.length;i++)
		{
			array[i] = count*50-array[i];
		}
		while(Gray>0)
		{
			Arrays.sort(array,Collections.reverseOrder());
			if(array[2]>0)
			{
				Gray--;
				array[0]--;
				array[1]--;
				array[2]--;
			}
			else
			{
				count++;
				for(int i=0;i<array.length;i++)
					array[i]+=50;
			}
		}
		return count;
	}
	
}