poj 2709 painter

题目要求

给定涂料，每套涂料含有3-12种不同的颜色（开始时候给定选用的颜料套的颜色数目），
且一套涂料中每种颜色均有50ml。且一套涂料中的任意三种不同的颜色各X ml混合都可以获得 灰色颜料 X ml。
  现在给定需要的各个颜色的数量（这些颜色都属于同一套颜料），以及需要的灰色颜色的数量。
求最少需要多少套颜料才能获得这些颜色。

题目分析

直觉告诉我们，使用贪心算法可以解决这个问题。通过使用最多量的颜色可以获得至少需要的颜
料的套数 minset, 用minset*50 减去这些颜色的数量，得到使用min_set的套数的颜料之后剩余的颜色的 数量。之后，使用贪心算法，每次选择剩余数量最多的三种颜色进行混合，这样做可以使得剩余的颜色的数目最
多，从而使得之后的配色有更多的选择；那么考虑每次混合数量最多的三种颜色的时候混合多少？
发现，每次只混合1 ml的灰色颜色可以保证正确性，而每次混合大于1ml的数量的灰色颜色，则无法保证正确性 （每次混合多少的灰色颜色应该是可以算出来的，但是不知道怎么去做。。。）

实现代码

    #include<iostream>

    #include<algorithm>

    #include<queue>

    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;

    }