WA 蒟蒻求助(带注释代码)
  • 板块P1528 切蛋糕
  • 楼主EllinY
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/8/19 14:53
  • 上次更新2023/10/27 14:36:35
查看原帖
WA 蒟蒻求助(带注释代码)
514936
EllinY楼主2022/8/19 14:53

真是太神奇了,没有TLE,反而WA了

#include<bits/stdc++.h>
using namespace std;
int n,m;
int c[51],t[51];//cake 
int p[1025];//person 
int sc,sp[1025];
//蛋糕总体积 & 每个人嘴巴大小的前缀和 
int l,r,mid,ans;
//二分答案专用变量组合 
int waste;
bool dfs(int pos){
//现在应当塞第 pos 个人的嘴,已浪费 waste 体积的蛋糕 
	if(pos==0) return 1;
	//已填满前 mid 个人的嘴,成功了  
	if(sc-waste<sp[mid]) return 0;
	//浪费了太多,剩下的蛋糕不够前 mid 个人吃了 
	for(int i=1;i<=n;i++){
		//蛋糕太小,塞不满 
		t[i]-=p[pos];
		//蛋糕被吃了一部分  
		if(t[i]<p[1]) waste+=t[i];
		//剩余的不够嘴最小的人吃了,只能浪费了 
		if(dfs(pos-1)) return 1;
		//去塞下一个人的嘴 
		if(t[i]<p[1]) waste-=t[i];
		t[i]+=p[pos];
		//回溯  
	}
	return 0;
}
int main(){
	cin>>n;
	int maxx=0;
	//最大的蛋糕 
	for(int i=1;i<=n;i++){
		cin>>c[i];
		sc+=c[i];
		maxx=max(maxx,c[i]);
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>p[i];
		sp[i]=sp[i-1]+p[i];
	}
	sort(p+1,p+m+1);
	//先喂嘴小的,能多喂几个 
	while(p[m]>maxx) m--;
	//嘴太大,最大的蛋糕都塞不满,只好不塞他的嘴了  
	r=m;
	while(l<=r){
		mid=(l+r)/2;
		waste=0;
		for(int i=1;i<=n;i++) t[i]=c[i];
		if(dfs(mid)){
			ans=mid;
			l=mid+1;
		}
		//成功了就记住答案,去试试能不能塞满更多人的嘴 
		else r=mid-1;
		//不成功,就只好降低要求,去塞少一点的人的嘴 
	}
	cout<<ans<<endl;
	//输出答案 
	return 0;
}

救救孩子!谢谢Thanks♪(・ω・)ノ!

2022/8/19 14:53
加载中...