#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函数那里,但是为什么前者返回错误,后者返回正确呢?