西部数码网站打不开,企信宝,找人做软件网站,wordpress cms 下载假设最多能满足 x x x个人#xff0c;那么这 x x x个人一定可以是按照每个人吃蛋糕的需求将他们从小到大排序后的前 x x x个人。#xff08;有两个人他们吃蛋糕的需求分别为 x 1 x_1 x1和 x 2 x_2 x2#xff0c;且 x 1 x 2 x_1x_2 x1x2#xff0c;如果…假设最多能满足 x x x个人那么这 x x x个人一定可以是按照每个人吃蛋糕的需求将他们从小到大排序后的前 x x x个人。有两个人他们吃蛋糕的需求分别为 x 1 x_1 x1和 x 2 x_2 x2且 x 1 x 2 x_1x_2 x1x2如果 x 2 x_2 x2可以出现在答案中那么 x 1 x_1 x1也一定能出现在答案中因为 x 1 x_1 x1的需求比 x 2 x_2 x2小一定可以填在 x 2 x_2 x2的位置。所以答案满足单调性我们可以通过二分答案检查 x x x是否可以满足。二分这部分的复杂度是 l o g 2 1024 10 log_2{1024}10 log2102410。
在这里可以有一个小优化如果某个人的需求比最大的蛋糕还要大那么无论如何是无法满足他的在下面的过程中不需要考虑这个人。
接下来就是通过 d f s dfs dfs来判断是否可以满足 x x x个人的需求。
dfs中我们需要两个参数分别记录还剩几个人需要满足 p e o peo peo、这次二分出的答案 m i d mid mid。当 p e o 1 peo1 peo1时即已经满足了所有人这个答案是可行的。接下来开始枚举所有蛋糕如果这个蛋糕剩下的大小足以满足第 p e o peo peo个人那就切下这个人需要的大小的蛋糕递归到下一个人。 n n n的大小是 20 20 20需要一些剪枝来降低复杂度。
一块蛋糕被切掉一部分之后如果它剩下的部分连需求最小的人都无法满足那么就可以说剩下的部分是被浪费的。如果蛋糕有用的部分总数-浪费不能满足前 x x x个人需求的和那么二分的这个答案一定不可行。
如果第 i i i个人的需求和第 i − 1 i-1 i−1个人相同由于我们第 i i i个人已经处理到了第 p o s pos pos块蛋糕处理第 i − 1 i-1 i−1个人的时候就不需要处理第 p o s pos pos块蛋糕前面的蛋糕了因为我们在处理第 i i i个人的需求时已经枚举了一遍前面一定没有符合第 i i i个人需求的。所以可以在 d f s dfs dfs时再加一个参数 p o s pos pos表示从第 p o s 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;
}
