自动搬运

查看原文

来自洛谷，原作者为

	shiroha **

搬运于2025-08-24 21:26:06，当前版本为作者最后更新于2019-11-09 05:58:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

此题算法Tag：二分查找、深度优先搜索、贪心、剪枝

分析

• 贪心：对于同样的蛋糕，相比于给嘴大的人吃，给嘴小的人吃可以满足更多人。优先将蛋糕喂给嘴小的人可以获得局部最优解。
• 判断：判断一个局部最优解是不是整体最优解，只能通过暴力的搜索的方式。但是这样的话会消耗很多的时间。
• 二分：此题答案可行域连续，可以使用二分查找确定答案，再由搜索验证答案是否合理以缩小区间直到可以确定最优解。
• 剪枝：为了避免TLE，还应对一些细节进行一些优化。比如：嘴比最大的蛋糕大的人是不可能满足的，应当直接剔除。

搜索

• 搜索之前，根据分析，将所有的人根据嘴的大小进行升序排列。如果有n个人可以被满足，那么这n个人一定是数组的前n个元素。
• 对待检验值进行DFS搜索。如果满足了它的需求，就递归搜索它的前一个人是否可以被剩下来的蛋糕满足。
• 如果嘴最小的人的需求也可以被满足，那么递归中止，验证通过；如果中途出现某人的需求不能被满足，那么就回溯到上一级递归。
• 如果找到了满足测试值人数的蛋糕分配方式，就直接退出查找，以避免不必要的性能浪费。

优化

• 求值备用：排列嘴大小之后要计算前缀和，可以方便后续的使用；读入蛋糕的时候需要计算最大的蛋糕和蛋糕总值以备使用。使用优先级队列存储蛋糕。
• 缩小区间：如果某人的嘴比最大的蛋糕还要大，那么根据题意，他的需求将永远无法得到满足。此时可以收紧二分查找区间以减少查找次数。
• 浪费蛋糕：如果某块蛋糕（或者被啃过的蛋糕）小于当前嘴最小的人的需求，那么此蛋糕将无法再发挥任何作用了，可以存储起来。
• 等大需求：因为对嘴的大小进行了排序，确保了先查找的嘴不小于后查找的嘴。若相邻两嘴大小相等，后者已经遍历了部分蛋糕数组才求出结果，等于说是已遍历部分的蛋糕一定不能满足要求。为了减少遍历，可以将此时的数组坐标传给下一级递归，在需求相等的下一级递归中跳过这些不可能的部分，以节约时间。

说明

• 设置非遍历终点的返回点时，应确保回溯代码可以正常执行。不规范的写法可能导致部分语句根本上是Unreachable的，无法执行到。
• 每一个递归层应当都有独立的wasted标志。因为它会根据每一层递归遍历到的蛋糕情况而被修改。
• 代码不规范，调试两行泪
• 其实这都是本人做题过程中遇到的问题或手抖犯下的错误

代码

#include <iostream>
#include <algorithm>

#define max(a,b) (a>b?a:b)
#define MIN_NEED mouth[1]

using namespace std;

int n,m;
int cake[55],mouth[1050];

int prefixSum[1050];                // 排序后嘴大小的前缀和
int maxCake,allCake;                // 最大蛋糕和所有蛋糕总和
int totalCake,needCake;             // 搜索：当前全部可用蛋糕和还需要的蛋糕
int wasteCake;                      // 优化：浪费的蛋糕渣

bool sub_DFS(int toTest, int origin)            // origin：遍历蛋糕数组的起点
{
    /* 结束递归 */
    if(toTest<1)
        return true;                            // 已经完成1~toTest的人的喂食，测试通过
    if(totalCake-wasteCake<needCake)
        return false;                           // 总蛋糕小于总需求，必然失败，停止搜索
    
    /* 搜索 */
    bool flag = false;
    for(int i=origin;i<=n;++i)                  // 遍历蛋糕，尝试将蛋糕喂给第toTest号人
    {
        if(cake[i]>=mouth[toTest])              
        {
            needCake-=mouth[toTest];            // 喂食：消耗蛋糕，满足需求                 
            totalCake-=mouth[toTest];
            cake[i]-=mouth[toTest];
            
            bool wasted = false;                // 回溯：是否使用了蛋糕渣优化
            if(cake[i]<MIN_NEED)                // 优化：蛋糕渣不能满足最低需求，不可用
            {
                wasteCake+=cake[i];             // 此蛋糕渣将被浪费，设置优化启动的标志
                wasted = true;
            }
            if(mouth[toTest]==mouth[toTest-1])  // 下一个测试对象的嘴和当前的嘴一样大
            { 
                if(sub_DFS(toTest-1,i))         // 优化：从当前的位置继续遍历蛋糕列表
                flag = true;                    // 优化：找到解决方案，就不再继续搜索
            }
            else if(sub_DFS(toTest-1,1))        // 无法优化，直接递归。
                flag = true;                    // 优化：同上分支

            /* 回溯 */
            if(wasted)                          // 若做了优化，则撤回         
                wasteCake-=cake[i];                
            cake[i]+=mouth[toTest];             // 撤回全部变化
            totalCake+=mouth[toTest];
            needCake+=mouth[toTest];

            if(flag) return true;
        }
    }

    /* 结束递归 */
    return false;                               // 无法找到合适的蛋糕，测试失败
}

inline bool DFS(int toTest)                     // DFS：检查答案toTest是否可行
{
    /* 准备变量 */
    totalCake = allCake;                          
    needCake = prefixSum[toTest];
    wasteCake = 0;

    /* 启动递归 */
    return sub_DFS(toTest,1);
}

int main()
{
    /* 优化读写 */
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    /* 初始化 */
    cake[0] = mouth[0] = 0;
    prefixSum[0] = 0;
    maxCake = allCake = 0;

    /* 读入 */
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>cake[i];
        maxCake=max(maxCake,cake[i]);           // 找到最大蛋糕并计算总值
        allCake+=cake[i];
    }
    cin>>m;
    for(int i=1;i<=m;++i)
        cin>>mouth[i];

    /* 预处理 */
    sort(mouth+1,mouth+1+m);                    // 贪心：先满足小嘴，进行升序排序
    for(int i=1;i<=m;++i)
        prefixSum[i]=prefixSum[i-1]+mouth[i];   // 计算前缀和    

    /* 二分查找 */
    int l=1,r=m;
    while(mouth[r]>maxCake)--r;                 // 优化：缩小二分查找范围
    int mid;
    while(l<=r)
    {
        mid = ((l+r)>>1);
        if(DFS(mid))l=mid+1;                 
        else r=mid-1;                       
    }
    cout<<r;                               

    return 0;
}

注释写的还算详细吧……就算文字说明的很屑应该也能看懂代码吧==

2019-11-09-5:55-A.M> 狗命要紧，洗洗睡罢（）

此题还可以使用神秘的随机化算法