POJ 2709 Painter-JAVA実現


JAVA実現POJ 2709——かかし
原題:http://poj.org/problem?id=2709
 
タイトル:
いくつかの色要件のml量を与え、最後の数はグレー要件量であり、グレーは任意の3つの異なる色の色から構成され、各顔料カートリッジには50 mlの色が与えられる.
少なくともいくつかの絵の具箱を与えて、必要な色を構成することができます
欲張りで解決し、まず満足する普通色に必要な最小箱数を求め、その後、残りの顔料を大きくから小さく並べ、その前の3種類は1 mlずつ取り出して1 mlの灰色を構成する(1 mlずつ取ると最適解に達する).
 
コード:
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;
	}
	
}