之前做其他二分题的时候调板子要调好久..在第一个板子和第二个板子之间还有return 1/0之间搞来搞去QaQ
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e4+50;
typedef long long LL;
LL cake[55],eatmouth[maxn];
LL eatsum[maxn];
LL n,m,l,r,mid;
LL total;//蛋糕总面积
LL chi;//吃的总数
LL dfs(LL peoide,LL pieces)//人数数目下标,蛋糕数量下标
{
if(peoide<=0) return 1;//0 蛋糕够吃了
//像填瓶子,先填嘴巴最大的,反之若先填小的,那么像填瓶子一下没有先填快的更容易填满,在程序中就是更快判断二分答案的可行性
for(LL i=pieces;i<=n;i++)
{
if(total<chi) return 0;//1 蛋糕不够吃 -->人多了
//记得回溯
if(cake[i]>=eatmouth[peoide])
{
cake[i]-=eatmouth[peoide];
total-=eatmouth[peoide];
chi-=eatmouth[peoide];
//剪枝
if(peoide-1<=0) return 1;//0 蛋糕够吃 -->人能下调
if(total<eatmouth[1]) return 0;//1 蛋糕不够吃 -->人多了
if(cake[i]<eatmouth[1]) total-=cake[i];
if(eatmouth[peoide]==eatmouth[peoide-1])
{
dfs(peoide-1,pieces);
}
else
{
dfs(peoide-1,1);
}
//回溯
if(cake[i]<eatmouth[1]) total+=cake[i];
chi+=eatmouth[peoide];
total+=eatmouth[peoide];
cake[i]+=eatmouth[peoide];
}
}
return 0;//1
}
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
cin>>n;
for(LL i=1;i<=n;i++) {cin>>cake[i];total+=cake[i];}
cin>>m;
for(LL i=1;i<=m;i++) {cin>>eatmouth[i];eatsum[i]+=eatsum[i-1]+eatmouth[i];}
LL tt=m;
while(eatsum[tt]>total) tt--;//减少二分枚举范围,就是减少dfs的过程
sort(cake+1,cake+n+1);
sort(eatmouth+1,eatmouth+1+m);
l=0,r=tt;
while(l<r)
{
mid=(l+r+1)>>1;
chi+=eatsum[mid];
if(dfs(mid,1)) l=mid;//上调人数
else r=mid-1; //下降人数
}
if(l==0) cout<<0<<endl;
else cout<<l<<endl;
return 0;
}