题意分析

题目描述了一个颜料套装购买问题，具体要求如下：

1. 颜料套装：

   • 每套包含$3$到$12$瓶$50$毫升的不同颜色颜料。
   • 颜料可以单独使用，也可以通过混合三种不同颜色各$X$毫升得到$X$毫升灰色颜料。

2. 需求输入：

   • $N$种颜色的需求量（毫升）。
   • 灰色颜料的需求量$G$（毫升）。

3. 目标：

   • 计算满足所有颜色需求和灰色需求的最少套装数量。
   • 灰色颜料可以通过任意三种不同颜色的组合混合得到。

示例解释

第一个测试用例：

• 颜色数$N=3$，需求量分别为$40$、$95$、$21$，灰色需求$G=0$。
• 最大需求为$95$，每套提供$50$毫升，$\lceil 95 / 50 \rceil = 2$套。
• 输出$2$。

解题思路

关键点分析

1. 灰色颜料混合：

   • 每$1$毫升灰色需要消耗$1$毫升三种不同颜色。
   • 灰色需求$G$会影响颜色的实际需求量。

2. 套装计算：

   • 每套提供$50$毫升每种颜色。
   • 最少套装数由以下两者决定：
     • 单独颜色需求的最大值（考虑灰色消耗）。
     • 灰色需求$G$对颜色消耗的额外要求。

3. 数学建模：

   • 设购买$k$套，则每种颜色最多可用$50 \times k$毫升。
   • 实际颜色需求为原始需求加上用于混合灰色的消耗。

解决步骤

1. 输入处理：

   • 读取颜色数$N$、各颜色需求和灰色需求$G$。

2. 灰色消耗分配：

   • 灰色需求$G$需要从$N$种颜色中分配，每种颜色最多贡献$G$次（因每次混合需三种颜色）。
   • 最小化最大颜色需求量：$\max(\text{颜色需求} + \text{灰色消耗}) \leq 50 \times k$。

3. 二分搜索：

   • 确定最少套装数$k$的范围（下界$\lceil \max(\text{颜色需求}) / 50 \rceil$，上界$\lceil (\max(\text{颜色需求}) + G) / 50 \rceil$）。
   • 对于每个$k$，检查是否能满足颜色和灰色需求。

4. 验证$k$的可行性：

   • 计算每种颜色的剩余量：$50 \times k - \text{原始需求}$。
   • 剩余量总和$\geq 3 \times G$（因每$1$毫升灰色消耗$3$毫升颜色）。
   • 每种颜色的剩余量$\geq$分配给灰色的量。

算法复杂度

• 时间复杂度：$O(\log (\max\_demand + G))$，其中$\max\_demand$为最大颜色需求。
• 空间复杂度：$O(N)$，存储颜色需求。

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
 
const int M=15;
int p[M];
 
bool cmp(int a,int b)
{
    return a>b;
}
 
int main()
{
    int n;
    int lea;
    int grey;
    int so;
    while(1)
    {
        lea=0;
        scanf("%d",&n);
        if(n==0)
            break;
        for(int i=0;i<n;i++)
        {
             scanf("%d",&p[i]);
             lea=max(lea,p[i]);
        }
        scanf("%d",&grey);
        if(lea%50==0)
            so=lea/50;
        else
            so=lea/50+1;
        for(int i=0;i<n;i++)
            p[i]=50*so-p[i];
        while(grey>0)
        {
            sort(p,p+n,cmp);
            if(p[2]==0)
            {
                so++;
                for(int i=0;i<n;i++)
                    p[i]+=50;
            }
            p[0]--;p[1]--;p[2]--;grey--;
        }
        printf("%d\n",so);
    }
    return 0;
}