二分+随机化贪心
首先我们有每次优先选择口小的人吃蛋糕的贪心策略。然后因为嘴巴的多少和填满嘴巴的困难程度存在单调关系，因此可以二分嘴巴的多少。而这个嘴巴个数为\(mid\)的时候，意味着我们需要满足前mid小的嘴巴都能被填满。判断能否填满时，可以用随机化贪心check。
此时贪心策略发生了变化。优先让大口吃蛋糕且对于每个人，只要见到比他嘴巴大的蛋糕就可以吃。
因为我们此时需要判断前mid小的嘴巴都能被填满，所以要使每个蛋糕都要满足，我们肯定要先让大的满足，不然越向后越难以满足，而小嘴巴如果吃剩下的都无法满足的话，那让小嘴巴先吃大嘴巴肯定就满足不了，随机化贪心其实就是快速枚举吃蛋糕的顺序
#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
int cak[1010011], per[1001011];
int tem[1001011];
bool check(int k)//check是否能使k个人吃上蛋糕
{
int t = 1000;
while (t--)
{
for (int i = 1; i <= n; i++)
tem[i] = cak[i];
random_shuffle(tem + 1, tem + 1 + n);//随机化打乱
int Flag = 1;
for (int i = k; i >= 1; i--)//前k个人。
{
int flag = 1;
for (int j = 1; j <= n; j++)
if (tem[j] >= per[i])
{
tem[j] -= per[i];
flag = 0;
break;
}
if (flag)
{
Flag = 0;
break;
}
}
if (Flag)
return 1;
}
return 0;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &cak[i]);
scanf("%d", &m);
for (int i = 1; i <= m; i++)
scanf("%d", &per[i]);//每个人的大小。切的蛋糕必须要比
sort(per + 1, per + 1 + m);
int l = 0, r = m;
while (l <= r)
{
int mid = (l + r) >> 1;
if ( check(mid) )
ans = mid, l = mid + 1;
else
r = mid - 1;
}
//先满足小口的人。
//二分最多能满足的人。
printf("%d", ans);
return 0;
}