poj-2709

141MS   Java  import java.util.Arrays;  import java.util.Comparator;  import java.util.Scanner;  public class Main{ private static final int BOTTLE_V = 50; private static final int V_TYPE_MAX = 12; private int mColorTypeNum; private int[] mColorRequireV; private int mGrayV; private Comparator mCmp; public void addRequireV(int V) { mColorRequireV[mColorTypeNum++] = V; } public void setGrayV(int V) { mGrayV = V; } public Main() { mColorRequireV = new int[V_TYPE_MAX]; mCmp = new reverseComparator(); reset(); } public class reverseComparator implements Comparator<Integer> { @Override public int compare(Integer p1, Integer p2) { return p2 - p1; } } public void solve() { Arrays.sort(mColorRequireV, 0, mColorTypeNum); int maxV = mColorRequireV[mColorTypeNum-1]; Integer colorLeft[] = new Integer[V_TYPE_MAX]; int i = 0; for (; BOTTLE_V*i < maxV; i++) { } int minBottleWithoutGray = i; // System.out.println(minBottleWithoutGray); for (i = 0; i < mColorTypeNum; i++) { colorLeft[i] = minBottleWithoutGray*BOTTLE_V - mColorRequireV[i]; // System.out.println(colorLeft[i]); } Arrays.sort(colorLeft, 0, mColorTypeNum, mCmp); int gray_V = mGrayV; while(true) { // System.out.println(gray_V); if (gray_V <= 0) { break; } if (colorLeft[2] <= 0) { // no enough 3 colors to mix gray, has add bottle  minBottleWithoutGray++; for (i = 0; i < mColorTypeNum; i++) { colorLeft[i] += BOTTLE_V; // System.out.println(colorLeft[i]); }   } // can mix colorLeft[2] V gray  int thisTimeGrayV; if (mColorTypeNum > 3 && colorLeft[3] > 0) {  thisTimeGrayV = colorLeft[2] - colorLeft[3] + 1; } else { thisTimeGrayV = colorLeft[2]; } // System.out.println(thisTimeGrayV); gray_V -= thisTimeGrayV; colorLeft[0] -= thisTimeGrayV; colorLeft[1] -= thisTimeGrayV; colorLeft[2] -= thisTimeGrayV; Arrays.sort(colorLeft, 0, mColorTypeNum, mCmp); } System.out.println(minBottleWithoutGray); reset(); } public void reset() { mColorTypeNum = 0; mGrayV = 0; } public static void main(String args[]) { Main solver = new Main(); Scanner scanner = new Scanner(System.in); while(true) { int colorTypeNum = scanner.nextInt(); if (colorTypeNum == 0) { return; } for (int i = 0; i < colorTypeNum; i++) { solver.addRequireV(scanner.nextInt()); } solver.setGrayV(scanner.nextInt()); solver.solve();   } }  }//3552K 141MS Java

这是一个贪婪的问题，但有一个非常重要的细节：

思路大致如下：

首先，不考虑gray，先看其他普通颜色至少需要多少套kit， 只要找一个i，i*500就能让i*50 是大于 (这些颜色中颜色数量最多的)最小值，

i 是能满足普通颜色数量要求的最小kit数量。

得到i后，就可以得到每种颜色还剩多少额外的量来得到gray的量，直接用i*50减去每种颜色的需求量，

贪得无厌的选择是，先用最多的三种颜色来获得gray色，

这里有一个重要的细节，比如ABCD有四种颜色，额外的量从大到小不等 V(A)>=V(B)>=V(C)>=V(D）

所以要从ABC三色中选择一定量的V来得到gray，起初想到V取C就可以了，后来发现不应该只是这样，

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

假设一个V1<V, 所以很有可能会有这样的情况:

ABC取V1后，额外量的大小关系变成了 V(D)>=V(A)-V1>=V(B)-V1>=V(C)-V1，

在这种情况下，根据贪婪的选择，不能再从ABC中选择gray，而应该从DAB中选择gray，

因此，从理论上讲，首先，我们应该以1ml为单位进行贪婪的选择，因为在从三种颜色中选择1ml与gray相匹配后，颜色之间的剩余大小关系可能会发生变化，

记住这个想法，也反映了计算机的步进运行.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

因此，每配1mlgray，就要重新排列颜色，然后选择新的前三种颜色。

但是，如果真的这样做了，那么铁定TLE，如果要求1000gray，那么就要做10000的重排，

因此，上述操作不能以1ml为单位进行，假设现在V(A)>=V(B)>=V(C)>=V(D)

可以肯定的是，最多可以从ABC取 V(C)-V(D) gray搭配ml， 颜色之间的大小关系不会改变，

因此，每次都可以取V(C)-V(D) + 1 配gray(前提是至少有4种颜色和 V(D)大于0)，

还会遇到V(C)(第三多颜色数量)已经为0，在这种情况下，必须增加kit数量，

每种颜色的数量会增加50，

根据上述流程循环，直到第一次分配>= gray要求 gray的数量.