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