74分求助(C++)(TLE了)
  • 板块P1528 切蛋糕
  • 楼主pencil
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/8/22 21:59
  • 上次更新2023/11/6 19:38:12
查看原帖
74分求助(C++)(TLE了)
137723
pencil楼主2020/8/22 21:59
#include<bits/stdc++.h>
using namespace std;
bool cmd(int a,int b){
	return a<b;
}
inline void read(int &a){
    a = 0;static char t = getchar();
    while(t>'9' || t<'0')t=getchar();
    while(t>='0' && t<='9'){
        a = (a << 3) + (a << 1) + (t^ 48);
        t=getchar();
    }
}
int mid;int a[60],b[1034],i,n,m,i2,ji[1034],qian[1034],zong,fei;
bool dfs(int start,int x){
	if(zong-fei<b[mid])  return 0;
	if(x==0) return true;
	int i,flag;
	for(i=start;i<=n;i++){
		if(a[i]>=b[x]){
			a[i]-=b[x];
			if(a[i]<a[1])
			fei+=a[i];
			if(b[x]==b[x-1])
			flag=dfs(i,x-1);
			else
			flag=dfs(1,x-1);
			if(a[i]<a[1])
			fei-=a[i];
			a[i]+=b[x];
			if(flag)  return 1;
		}
	}
	return 0;
}
int main(){
	int big;
	cin>>n;
	for(i=1,big=-1;i<=n;i++){
		//scanf("%d",&a[i]);
		read(a[i]);
		big=max(big,a[i]);zong+=a[i];
	} 
	cin>>m;
	for(i=1;i<=m;i++) {
		read(b[i]);
		//scanf("%d",&b[i]);
	}
//	sort(a+1,a+n+1,cmd);
	sort(b+1,b+m+1,cmd);
	for(i=m;i!=0;i--) if(b[i]<=big) break;
	m=i;
	int r=m,l=1,shu=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(dfs(1,mid))
		l=mid+1,shu=mid;
		else{
			r=mid-1;
		}
	}
	cout<<shu;
	return 0;
}
2020/8/22 21:59
加载中...