贴代码网址太卡了.在这挂下查错
作者:
小菜鸡UP
,
2020-07-15 22:40:30
,
所有人可见
,
阅读 929
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2020;
typedef int 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<1) return 1;// 蛋糕够吃了 人少了 上调
//像填瓶子,先填嘴巴最大的,反之若先填小的,那么像填瓶子一下没有先填快的更容易填满,在程序中就是更快判断二分答案的可行性
for(LL i=pieces;i<=n;i++)
{
if(total<chi) return 0;// 蛋糕不够吃 -->人多了 下调
if(peoide<1) return 1;// 蛋糕够吃 -->人少了 上调
//记得回溯
if(cake[i]>=eatmouth[peoide])
{
cake[i]-=eatmouth[peoide];
total-=eatmouth[peoide];
chi-=eatmouth[peoide];
//剪枝
if(total<eatmouth[1]&&peoide!=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 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];}
sort(cake+1,cake+n+1);
sort(eatmouth+1,eatmouth+1+m);
while(eatmouth[m]>total) m--;//减少二分枚举范围,就是减少dfs的过程
for(LL i=1;i<=m;i++)
eatsum[i]=eatsum[i-1]+eatmouth[i];
l=0,r=m;
//<=x的 前面的数
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;
}
tql
哪个题?
https://www.luogu.com.cn/problem/P1528