求助!
查看原帖
求助!
486441
13833925596mm楼主2022/10/20 12:44
#include <bits/stdc++.h>
using namespace std;
int a[51],b[1025],n,m,man=0,sum=0,bsum[1025],c[1025],lflf=0;
bool dfs(int u,int x){
	if(x==0) return true;
	if(sum-lflf<bsum[x]) return false;
	for(int i=u;i<=n;i++){
		if(a[i]>=b[x]){
			a[i]-=b[x];
			if(a[i]<b[1]) lflf+=a[i];
			if(b[x]==b[x-1]){
			    if(dfs(i,x-1)) return true;
			}
			else if(dfs(1,x-1)) return true;
			if(a[i]<b[1]) lflf-=a[i];
			a[i]+=b[x];
		}
	}
	return false;
}
int main(){
	cin>>n;
	int maxn=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
		maxn=max(maxn,a[i]);
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>c[i];
	}
	sort(c+1,c+1+m);
	bsum[1]=c[1];
	for(int i=2;i<=n;i++) bsum[i]=bsum[i-1]+c[i];
	while(c[m]>maxn) m--;
	int l=1,r=m,mid;
	while(l<=r){
		mid=(l+r)/2;
		for(int i=1;i<=m;i++) b[i]=c[i];
        lflf=0;
		if(dfs(1,mid)){
			l=mid+1;
			man=mid;
		}
		else r=mid-1;
	}
	cout<<man;
	return 0;
}
2022/10/20 12:44
加载中...