记录编号	176518	评测结果	AAAAAAAAAAAA
题目名称	882.栅栏的木料	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.038 s
提交时间	2015-08-09 08:13:41	内存使用	0.25 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
int ans,waste,s,n,m,l,r,mid,a[1111],w[1111],sum[1111];
bool flag;
void dfs(int j,int p)
{
	for(int i=j;i<=n;++i)
		if(a[i]>=w[p])
		{
			if(p==1)
			{		
				flag=1;
				return;
			}
			a[i]-=w[p];
			if(a[i]<w[1])
			{
				waste+=a[i];
				if(waste+sum[mid]>s)
				{
					waste-=a[i];
					a[i]+=w[p];
					continue;
				}
				if(w[p]==w[p-1])
					dfs(i,p-1);
				else
					dfs(1,p-1);
				waste-=a[i];				
			}
			else
			{
				if(waste+sum[mid]>s)
				{
					a[i]+=w[p];
					continue;
				}
				if(w[p]==w[p-1])
					dfs(i,p-1);
				else
					dfs(1,p-1);
			}
			a[i]+=w[p];
			if(flag)
				return;	
		}
}
int main()
{
	freopen("fence8.in","r",stdin);
	freopen("fence8.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		s+=a[i];
	}
	scanf("%d",&m);
	for(int i=1;i<=m;++i)
		scanf("%d",&w[i]);
	sort(a+1,a+n+1);
	sort(w+1,w+m+1);
	for(int i=1;i<=m;++i)
		sum[i]=sum[i-1]+w[i];
	r=m;
	while(l<=r)
	{
		flag=0;
		mid=(l+r)>>1;
		dfs(1,mid);
		if(flag)
		{
			l=mid+1;
			ans=mid;
		}
		else
			r=mid-1;
	}
	printf("%d",ans);
}