TLE,求助!
查看原帖
TLE,求助!
1126200
noWAnoWA楼主2024/7/27 16:46
#include<bits/stdc++.h>
using namespace std;
int tot,last,s[1001],m,a[1001],b[1001],n,sum[1001];
bool dfs(int step,int st){
	if(step==0) return true ;
	if(tot-last<s[step]) return false ;
	bool flag=false;
	for(int i=st;i<=m;i++){
		if(a[i]>=b[step]){
			a[i]-=b[step];tot-=b[step];
			if(a[i]<b[1]) last+=a[i];
			if(b[step]==b[step-1]) flag=dfs(step-1,st);
			else flag=dfs(step-1,1) ;	
			if(a[i]<b[1]) last-=a[i];
			a[i]+=b[step],tot+=b[step];
			if(flag) return true;
		}
	}
	return false;
}
int main(){
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		tot+=a[i];
	}
	cin>>n;
	for(int i=1;i<=n;i++) cin>>b[i];
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+b[i];
	while(sum[n]>tot&&n) n--;
	int l=1,r=n,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(dfs(mid,1)) l=mid+1;
		else r=mid-1;
	}
	cout<<l-1;
	return 0;
}
2024/7/27 16:46
加载中...