Luogu P1528 切蛋糕 || SCOI2005 栅栏

假设最多能满足$x$个人，那么这$x$个人一定可以是按照每个人吃蛋糕的需求将他们从小到大排序后的前$x$个人。（有两个人他们吃蛋糕的需求分别为$x_1$和$x_2$，且$x_1<x_2$，如果$x_2$可以出现在答案中，那么$x_1$也一定能出现在答案中，因为$x_1$的需求比$x_2$小，一定可以填在$x_2$的位置）。所以答案满足单调性，我们可以通过二分答案检查$x$是否可以满足。二分这部分的复杂度是$lo{g}_{2}1024=10$。

在这里可以有一个小优化，如果某个人的需求比最大的蛋糕还要大，那么无论如何是无法满足他的，在下面的过程中不需要考虑这个人。

接下来就是通过$dfs$来判断是否可以满足$x$个人的需求。

dfs中我们需要两个参数，分别记录还剩几个人需要满足（$peo$）、这次二分出的答案（$mid$）。当$peo<1$时，即已经满足了所有人，这个答案是可行的。接下来开始枚举所有蛋糕，如果这个蛋糕剩下的大小足以满足第$peo$个人，那就切下这个人需要的大小的蛋糕，递归到下一个人。$n$的大小是$20$，需要一些剪枝来降低复杂度。

一块蛋糕被切掉一部分之后，如果它剩下的部分连需求最小的人都无法满足，那么就可以说剩下的部分是被浪费的。如果蛋糕有用的部分（总数-浪费）不能满足前$x$个人需求的和，那么二分的这个答案一定不可行。

如果第$i$个人的需求和第$i-1$个人相同，由于我们第$i$个人已经处理到了第$pos$块蛋糕，处理第$i-1$个人的时候，就不需要处理第$pos$块蛋糕前面的蛋糕了，因为我们在处理第$i$个人的需求时已经枚举了一遍，前面一定没有符合第$i$个人需求的。所以可以在$dfs$时再加一个参数$pos$，表示从第$pos$块蛋糕开始枚举，这个参数就是为了这个剪枝的。

#include <bits/stdc++.h>
#define A 1025using namespace std;
int n, m, cake[A], tcake[A], need[A], cake_max, poss;
int sum[A], cake_sum, waste;
bool dfs(int peo, int x, int pos) {if (peo < 1) return true;if (cake_sum - waste < sum[x]) return false;for (int i = pos; i <= n; i++) {if (need[peo] <= tcake[i]) {tcake[i] -= need[peo];if (tcake[i] < need[1]) waste += tcake[i];if (need[peo] == need[peo - 1]) {if (dfs(peo - 1, x, i)) return true;}else if (dfs(peo - 1, x, 1)) return true;if (tcake[i] < need[1]) waste -= tcake[i];tcake[i] += need[peo];}}return false;
}int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> cake[i];cake_sum += cake[i];cake_max = max(cake_max, cake[i]);}cin >> m;for (int i = 1; i <= m; i++) cin >> need[i];sort(cake + 1, cake + n + 1);sort(need + 1, need + m + 1);poss = m;for (int i = 1; i <= m; i++) {sum[i] = sum[i - 1] + need[i];if (need[i] > cake_max) {poss = i;break;}}m = poss;int l = 0, r = m, mid, ans;while (l <= r) {mid = (l + r) / 2;memcpy(tcake, cake, sizeof cake);waste = 0;if (dfs(mid, mid, 1)) {l = mid + 1;ans = mid;}else r = mid - 1;}cout << ans << endl;
}