前言
蒟弱本来是在亿万年前做二分答案专题栅栏的，由于数据水所以过掉了，后来发现有一个数据加强版，也就是本题，于是爆T了...过了有个五六个月回来填坑了...现在开O2是在最优解第一个（自豪ing
题目描述
有 \(n\) 块 大小分别为 \(a_i\) 的蛋糕，分给 \(m\) 个嘴大小分别为 \(b_i\) 的人，但是蛋糕只能以整块的形式给人，求最多给多少人。
思路
很明显，答案在排序之后具有单调性，所以可以二分能够分给多少人，但二分并没有一个明确的套路切蛋糕，所以需要进行深搜；
于是来考虑最优贪心策略：
- 首先将所有蛋糕和嘴的大小排序，优先喂嘴小的人；
对应着这两行：
n=read();F(i,1,n)a[i]=read(),tot+=a[i];std::sort(a+1,a+n+1);
m=read();F(i,1,m)b[i]=read();std::sort(b+1,b+m+1);
- 排完序后，考虑缩小二分范围，我们从小到大求得嘴大小的前缀和，如果到第 \(i\) 个人的嘴大小总和 \(pre_i\) 超过了上面求出的蛋糕大小总和 \(tot\)，或者 \(b_i>a[n]\)，那么到这里无论如何切都无法满足条件，二分的最大边界就是 \(i-1\) 了。另外，如果蛋糕总和都比最小的嘴小，那么一个也不能满足。
对应着这三行：
if(tot<b[1]){pi(0);return 0;}
F(i,1,m){pre[i]=pre[i-1]+b[i];if(pre[i]>tot||b[i]>a[n]){cnt=i-1;break;}}
if(!cnt)cnt=m;
我们开始二分+深搜：
- 在深搜过程中，枚举能够切下够这口嘴吃的蛋糕，切掉后蛋糕总大小要减去嘴的大小。如果这块蛋糕切剩下的不够最小嘴的，那么就相当于这块蛋糕没有用了，蛋糕总大小要再减去没有用的这部分。
也就是这样：
if(a[i]>=b[x]){
a[i]-=b[x];tot-=b[x];
if(a[i]<b[1])tot-=a[i];
}
- 显然，当剩下几张嘴的总大小比剩下几块蛋糕的总大小还要大时，方案是不符合的。
也就是这句：
if(pre[x]>tot)return 0;
- 当当前搜索到的这口嘴与下一个要搜索的嘴大小相同时，既然已经枚举到了第 \(i\) 块蛋糕，说明第 \(i\) 块蛋糕之前的蛋糕对于这个大小的嘴都是没有正确方案的，于是搜索下一口嘴时就可以直接从第 \(i\) 块蛋糕枚举。
这句话的实现长这样：
if(b[x]==b[x-1])fl=check(x-1,i);else fl=check(x-1,1);
最后无论有没有正确方案都要记得回溯啊！
if(a[i]<b[1])tot+=a[i];
a[i]+=b[x];tot+=b[x];
到最后如果枚举完所有的蛋糕都没有正确方案，就可以直接 \(return\ 0\) 了。
于是本题就可以愉快的结束了～
CODE
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
namespace EMT{
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void pi(int x){pf("%d",x);}inline void pn(){pf("\n");}inline void ps(int a[],int size){F(i,1,size)pi(a[i]);pn();}
int n,m,a[55],b[1100],ans,cnt,ws,tot,pre[1100];
inline bool check(int x,int st){
if(!x)return 1;
if(pre[x]>tot)return 0;
bool fl=0;
F(i,st,n){
if(a[i]>=b[x]){
a[i]-=b[x];tot-=b[x];
if(a[i]<b[1])tot-=a[i];
if(b[x]==b[x-1])fl=check(x-1,i);else fl=check(x-1,1);
if(a[i]<b[1])tot+=a[i];
a[i]+=b[x];tot+=b[x];
if(fl)return 1;
}
}return 0;
}
inline short main(){
n=read();F(i,1,n)a[i]=read(),tot+=a[i];std::sort(a+1,a+n+1);
m=read();F(i,1,m)b[i]=read();std::sort(b+1,b+m+1);;;;;;
if(tot<b[1]){pi(0);return 0;}
F(i,1,m){pre[i]=pre[i-1]+b[i];if(pre[i]>tot||b[i]>a[n]){cnt=i-1;break;}}
if(!cnt)cnt=m;
int l=1,r=cnt,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid,1))l=mid+1,ans=mid;
else r=mid-1;
}
pi(ans);
return 0;
}
}
signed main(){return EMT::main();}
