poj 2709 painter

题目要求

   给定涂料，每套涂料含有3-12种不同的颜色（开始时候给定选用的颜料套的颜色数目），

且一套涂料中每种颜色均有50ml。且一套涂料中的任意三种不同的颜色各X ml混合都可以获得 灰色颜料 X ml。

  现在给定需要的各个颜色的数量（这些颜色都属于同一套颜料），以及需要的灰色颜色的数量。

求最少需要多少套颜料才能获得这些颜色。

题目分析

  直觉告诉我们，使用贪心算法可以解决这个问题。通过使用最多量的颜色可以获得至少需要的颜

料的套数 minset, 用minset*50 减去这些颜色的数量，得到使用min_set的套数的颜料之后剩余的颜色的 数量。之后，使用贪心算法，每次选择剩余数量最多的三种颜色进行混合，这样做可以使得剩余的颜色的数目最

多，从而使得之后的配色有更多的选择；那么考虑每次混合数量最多的三种颜色的时候混合多少？

发现，每次只混合1 ml的灰色颜色可以保证正确性，而每次混合大于1ml的数量的灰色颜色，则无法保证正确性 （每次混合多少的灰色颜色应该是可以算出来的，但是不知道怎么去做。。。）

实现代码

#include
     
          #include
      
           #include
       
            using namespace std;    #define MAX_NUM 13    int paint[MAX_NUM];    int bottle[MAX_NUM];    bool cmp(const int a, const int b){        return a > b;    }    int Resolve(int n, int gray_volume){        sort(paint, paint + n, cmp);        int min_bot = paint[0] / 50 + int(paint[0] % 50 != 0);        int result = min_bot;        if (gray_volume <= 0){            return result;        }        for (int i = 0; i < n; i++){            paint[i] = min_bot * 50 - paint[i];        }        sort(paint, paint + n, cmp);        while (gray_volume){            if (paint[2] == 0){                for (int i = 0; i < n; i++){  //如果还有剩余的颜色的数目小于三种，则增加一套颜料                    paint[i] += 50;                }                result++;            }            paint[0] --;   //每次只减少 1ml的量            paint[1] --;            paint[2] --;            gray_volume--;            sort(paint, paint + n, cmp);        }        return result;    }    int main(){        int n, gray;        while (true){            cin >> n;            if (n == 0){                break;            }            for (int i = 0; i < n; i++){                cin >> paint[i];            }            cin >> gray;            cout << Resolve(n, gray) << endl;        }        return 0;    }