题解 P1528 【切蛋糕】
此题算法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> 狗命要紧，洗洗睡罢（）