感觉是自己二分板子的问题(阿这
查看原帖
感觉是自己二分板子的问题(阿这
287539
勇敢的菜鸡楼主2020/7/15 21:34

之前做其他二分题的时候调板子要调好久..在第一个板子和第二个板子之间还有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;
}


2020/7/15 21:34
加载中...