check错误
查看原帖
check错误
356454
TangWK楼主2021/10/4 23:20
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int n,m;
int mm[1001],nn[1001],sun[1001];
int l,r,mid;
int wast,sum=0;
/**/
bool check(int las,int x) {
	if(x<=0)
		return 1;
	if(sum-wast<sun[mid])
		return 0;
	int i;
	for(i=las;i<=m;++i) {
		if(mm[i]>=nn[x]) {
			mm[i]-=nn[x];
			if(mm[i]<nn[1])
				wast+=mm[i];
			if(nn[x-1]==nn[x])
				if(check(i,x-1)==1)
					return 1;
			else if(check(1,x-1)==1)
				return 1;
			if(mm[i]<nn[1])
				wast-=mm[i];
			mm[i]+=nn[x];
		}
	}
	
	//,printf("why?\n");
	return 0;//,printf("!");
	//;
}

int main() {
	
	scanf("%d",&m);
	int i;
	priority_queue< int,vector<int>,greater<int> > s1;
	int x;
	for(i=1;i<=m;++i) {
		scanf("%d",&x);
		s1.push(x);
		sum+=x;
	}
	for(i=1;i<=m;++i)
		mm[i]=s1.top(),s1.pop();
	scanf("%d",&n);
	for(i=1;i<=n;++i) {
		scanf("%d",&x);
		s1.push(x);
	}
	for(i=1;i<=n;++i) {
		nn[i]=s1.top(),s1.pop();
	}
	//现在全部都是有序的
	sun[0]=0;
	//n=unique(nn+1,nn+1+n)-nn;
	for(i=1;i<=n;++i) {
		sun[i]=sun[i-1]+nn[i];
	} 
	while(sum<sun[n]&&n>=0)
		--n;
	/**/
	l=1,r=n;
	//printf("%d %d\n",m,n);
	while(l<=r) {
		//printf("!");
		mid=(l+r)>>1;
		wast=0;
		if(check(1,mid))
			l=mid+1;
		else
			r=mid-1;
		/*
		printf("%d\n",mid);
		for(i=1;i<=m;++i)
			printf("%d ",mm[i]);
		puts("");
		*/
		//printf("lr %d %d\n",l,r);
	}
	printf("%d\n",l-1);
	return 0;
}

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int n,m;
int mm[1001],nn[1001],sun[1001];
int l,r,mid;
int wast,sum=0;
/**/
bool check(int las,int x) {
	//printf("%d %d %d %d %d\n",las,x,wast,sum,sun[mid]);
	if(x<=0)
		return 1;
	if(sum-wast<sun[mid])
		return 0;
	int i;
	bool p;
	for(i=las;i<=m;++i) {
		if(mm[i]>=nn[x]) {
			//wast+=mm[i]-nn[x];
			mm[i]-=nn[x];
			if(mm[i]<nn[1])
				wast+=mm[i];
			if(nn[x-1]==nn[x])
				p=check(i,x-1);
			else
				p=check(1,x-1);
			if(mm[i]<nn[1])
				wast-=mm[i];
			mm[i]+=nn[x];
			if(p)
				return 1;
		}
	}
	
	
	return 0;//,printf("!");
	//;
}

int main() {
	
	scanf("%d",&m);
	int i;
	priority_queue< int,vector<int>,greater<int> > s1;
	int x;
	for(i=1;i<=m;++i) {
		scanf("%d",&x);
		s1.push(x);
		sum+=x;
	}
	for(i=1;i<=m;++i)
		mm[i]=s1.top(),s1.pop();
	scanf("%d",&n);
	for(i=1;i<=n;++i) {
		scanf("%d",&x);
		s1.push(x);
	}
	for(i=1;i<=n;++i) {
		nn[i]=s1.top(),s1.pop();
	}
	//现在全部都是有序的
	sun[0]=0;
	//n=unique(nn+1,nn+1+n)-nn;
	for(i=1;i<=n;++i) {
		sun[i]=sun[i-1]+nn[i];
	} 
	while(sum<sun[n]&&n>=0)
		--n;
	/**/
	l=1,r=n;
	//printf("%d %d\n",m,n);
	while(l<=r) {
		//printf("!");
		mid=(l+r)>>1;
		wast=0;
		if(check(1,mid))
			l=mid+1;
		else
			r=mid-1;
		/*
		printf("%d\n",mid);
		for(i=1;i<=m;++i)
			printf("%d ",mm[i]);
		puts("");
		*/
		//printf("lr %d %d\n",l,r);
	}
	printf("%d\n",l-1);
	return 0;
}

区别在check函数那里,但是为什么前者返回错误,后者返回正确呢?

2021/10/4 23:20
加载中...