记录编号	462236	评测结果	AAAAAAAAAAAA
题目名称	882.栅栏的木料	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2017-10-21 17:02:19	内存使用	0.32 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int maxn=60;
const int maxm=1030;
int n,m;
int mu[maxn],re[maxn];
int data[maxm];
int s[maxm];
int wast,rest;
inline bool ok(int sum,int p){
	if(sum<1)return true;
	if(wast>rest)return false;
	//可行性剪枝，如果浪费的木材比剩下的木材还多肯定不可行；
	for(int i=p;i<=n;i++){
		if(mu[i]<data[sum])continue;
		if(mu[i]>=data[sum]){
			mu[i]-=data[sum];
			if(mu[i]<data[1])wast+=mu[i];
			if(data[sum]==data[sum-1]){if(ok(sum-1,i))return true;}
			else if(ok(sum-1,1))return true;
			if(mu[i]<data[1])wast-=mu[i];
			mu[i]+=data[sum];
		}
	}
	return false;
}
int main(){
	freopen("fence8.in","r",stdin);
	freopen("fence8.out","w",stdout);
	n=read();
	int tot=0;
	for(int i=1;i<=n;i++)re[i]=mu[i]=read(),tot+=mu[i];
	m=read();
	for(int i=1;i<=m;i++)data[i]=read();
	sort(mu+1,mu+n+1);sort(data+1,data+m+1);
	sort(re+1,re+n+1);
	for(int i=1;i<=m;i++)s[i]=s[i-1]+data[i];
	while(s[m]>tot)m--;
	int l=0,r=m;
	while(l+1<r){
		int mid=(l+r)>>1; 
		wast=0;rest=tot-s[mid];
		if(ok(mid,1))l=mid;
		else r=mid;
		for(int i=1;i<=n;i++)mu[i]=re[i];
	}
	if(ok(r,1))printf("%d\n",r);
	else printf("%d\n",l);
	return 0;
}