POJ2709 染料贪心

题意：

要搭配出来n种颜料，每种颜料要用mi升，除了这n种颜色还有一个合成灰色的毫升数，灰色是由三种不同的颜色合成的，三种m m m 的不同颜色能合成m升灰色，然后问你满足要求至少要多少盒颜色，这个1盒的定义是：一盒里面有n种颜色，每种50ml.

思路：

先把所有的这n中颜色的最小需要合数求出来，然后在处理灰色，处理灰色的时候可以1升1升的合成，每次去当前最大的三个来合成1升，如果最大的三个有0的，那么就再来一盒（也就是一套），千万不要直接把最大的个颜色直接一下用完，要1升一升用，但是有小优化，就是用第三盒和第四和的差，如果相等就用1，这样感觉会快一点，我是这样想的，ac了，但是貌似又不优化都是0ms过吧，题目简单，但是挺好。

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int cc[15];

int tt[15];

int main ()

{

    int i ,j ,n ,hui;

    while(~scanf("%d" ,&n) && n)

    {

        int max = 0;

        for(i = 1 ;i <= n ;i ++)

        {

            scanf("%d" ,&cc[i]);

            for(j = 0 ;;j++)

            if(j * 50 >= cc[i])

            {

                if(max < j) max = j;

                cc[i] = j * 50 - cc[i];

                tt[i] = j;

                break;

            }

        }

        for(i = 1 ;i <= n ;i ++)

        cc[i] += (max-tt[i]) * 50;

        scanf("%d" ,&hui);

        while(hui>0)

        {

            sort(cc + 1 ,cc + n + 1);

            if(!cc[n] || !cc[n-1] || !cc[n-2])

            {

                max ++;

                for(j = 1 ;j <= n ;j ++)

                cc[j] += 50;

            }

            int tmp;

            if(n == 3) tmp = cc[n-2];

            else if(cc[n-2] == cc[n-3]) tmp = 1;

            else tmp = cc[n-2] - cc[n-3];

            hui -= tmp;

            cc[n] -= tmp;

            cc[n-1] -= tmp;

            cc[n-2] -= tmp;

        }

    printf("%d\n" ,max);

    }

    return 0;

}

巴特西

POJ2709 染料贪心

最新文章

热门文章