洛谷P1528切蛋糕题解

Link To Problem

题意概述

有 $n$ 块蛋糕， $m$ 个人。可以用刀切蛋糕，但他不能把两块蛋糕拼起来。给定每个人需要蛋糕的大小，且每人只能有一块蛋糕。
请问怎样切蛋糕，才能满足最多的人。

思考

“满足最多”,一看就知道这题是二分啦！二分是个好东西，可以把最优化问题转化为可行性问题。
如何 check 呢？可以暴力 dfs 哦.

剪枝

1. 蛋糕浪费
   当他不能满足任何人的嘴，他就被浪费了。
2. 无用蛋糕
   当他不能满足任何人的嘴，他就是无用的。
3. 贪心排序
   按照胃口大小排序，优先满足小胃口的。
4. 胃口过大
   当胃口大于最大蛋糕时，这个人可以直接扔掉。
5. 记录坐标
   若一个蛋糕不能满足比他小的人，也不能满足他，可以从下一个开始。
   平均复杂度会开根号。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,cake[55],mouth[1050],prefixSum[1050],maxCake,allCake,totalCake,needCake,wasteCake;
bool dfs(int toTest, int origin)
{
    if(toTest<1) return true;
    if(totalCake-wasteCake<needCake) return false;
    bool flag = false;
    for(int i=origin;i<=n;++i)
    {
        if(cake[i]>=mouth[toTest])              
        {
            needCake-=mouth[toTest];
            totalCake-=mouth[toTest];
            cake[i]-=mouth[toTest];
            bool wasted = false;
            if(cake[i]<mouth[1])
            {
                wasteCake+=cake[i];
                wasted = true;
            }
            if(mouth[toTest]==mouth[toTest-1])
            { 
                if(dfs(toTest-1,i))
                flag = true;
            }
            else if(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 check(int toTest)
{
    totalCake = allCake;                          
    needCake = prefixSum[toTest];
    wasteCake = 0;
    return dfs(toTest,1);
}
int main()
{
    cake[0] = mouth[0] = 0;
    prefixSum[0] = 0;
    maxCake = allCake = 0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",cake+i);
        maxCake=max(maxCake,cake[i]);
        allCake+=cake[i];
    }
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
        scanf("%d",mouth+i);
    sort(mouth+1,mouth+m+1);
    sort(cake+1,cake+n+1,greater<int>());
    for(int i=1;i<=m;++i) prefixSum[i]=prefixSum[i-1]+mouth[i];
    int l=1;
    int r = m;//lower_bound(mouth+1,mouth+m+1,r) - 1 - mouth;
    //while(mouth[r]>maxCake)--r;
    int mid;
    while(l<=r)
    {
        mid = ((l+r)>>1);
        if(check(mid))l=mid+1;                 
        else r=mid-1;                       
    }
    printf("%d",r);
    return 0;
}