TLE:90分,不知道还能怎么改(救救孩子吧)
查看原帖
TLE:90分,不知道还能怎么改(救救孩子吧)
757546
NingMeng_yang楼主2024/11/7 19:26
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+7;
int m;
int s[N];
int n;
int e[N];
int sum[N];
int cnt,mid;
inline bool dfs(int x,int l)
{
	if(x==0) return 1;
	if(cnt<sum[x]) return 0;
	bool bl=false;
	for(register int i=l;i<=m;++i)
	{
		if(s[i]>=e[x])
		{
			s[i]-=e[x];cnt-=e[x];
			if(s[i]<e[1]) cnt-=s[i];
			if(e[x-1]==e[x]) bl=dfs(x-1,i);
			else bl=dfs(x-1,1);
			if(s[i]<e[1]) cnt+=s[i];
			s[i]+=e[x];cnt+=e[x];
			if(bl) return true;
		}
	}
	return false;
}
signed main()
{
	scanf("%d", &m);
	for(register int i=1;i<=m;++i) scanf("%d",&s[i]),cnt+=s[i];
	sort(s+1,s+m+1);
	scanf("%d",&n);
	for(register int i=1;i<=n;++i) scanf("%d",&e[i]);
	sort(e+1,e+n+1);
	if(cnt<e[1])
	{
		cout<<0<<endl;
		return 0;
	}
	int idx=0;
	for(register int i=1;i<=n;++i)
	{
		sum[i]=sum[i-1]+e[i];
		if(sum[i]>cnt||e[i]>s[n])
		{
			idx=i-1;
			break;
		}
	}
	if(!idx) idx=n;
	int l=1,r=idx,ans=0;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(dfs(mid,1)) l=mid+1,ans=mid;
		else r=mid-1;
	}
	printf("%d",ans);
	return 0;
}

最后一个点TLE了, 希望能有人指一条明路。 (求求了)

2024/11/7 19:26
加载中...