记录编号	75804	评测结果	AAAAAAAAAAAA
题目名称	882.栅栏的木料	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2013-10-28 22:06:16	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int SIZEN=55;
const int SIZER=1024;
int rail[SIZER+1]={0},board[SIZEN+1]={0};
int pres[SIZER+1]={0};
int n,r;//n块原料,r块需求
int max_waste;
int boardsum=0;
int minrail=0x7ffff;
bool cmp_max(int a,int b){
	return a>b;
}
void read(void){
	int i;
	scanf("%d",&n);
	int maxboard=0;
	for(i=1;i<=n;i++) scanf("%d",&board[i]),boardsum+=board[i],maxboard=max(maxboard,board[i]);
	sort(board+1,board+1+n,cmp_max);
	scanf("%d",&r);
	int temp=0;
	for(i=1;i<=r;i++) scanf("%d",&rail[i]),minrail=min(minrail,rail[i]);
	sort(rail+1,rail+1+r);
	for(i=1;i<=r;i++) pres[i]=pres[i-1]+rail[i];
	for(i=1;i<=r;i++) if(rail[i]>maxboard) temp++;
	r-=temp;
}
int limit;//当前尝试:1~limit这些rail能否切出
int nowcut[SIZEN]={0};
int now_waste;
bool DFS(int xr,int last_dec){//r:rail
	if(xr<1) return true;
	if(now_waste>max_waste) return false;
	int i;
	int start,temp;
	if(rail[xr]==rail[xr+1]) start=last_dec;
	else start=1;
	for(i=start;i<=n;i++){
		if(nowcut[i]+rail[xr]<=board[i]){
			nowcut[i]+=rail[xr];
			temp=now_waste;
			if(board[i]-nowcut[i]<minrail) now_waste+=board[i]-nowcut[i];
			if(DFS(xr-1,i)) return true;
			nowcut[i]-=rail[xr];
			now_waste=temp;
		}
	}
	return false;
}
bool check(int x){
	limit=x;
	max_waste=boardsum-pres[x];
	now_waste=0;
	if(max_waste<0) return false;
	memset(nowcut,0,sizeof(nowcut));
	return DFS(limit,1);
}
int find(int left,int right){
	if(left==right) return left;
	int mid=(left+right)%2?(left+right)/2+1:(left+right)/2;
	if(check(mid)){//mid可行,说明结果不小于mid
		return find(mid,right);
	}
	else return find(left,mid-1);
}
int main(){
	freopen("fence8.in","r",stdin);
	freopen("fence8.out","w",stdout);
	read();
	printf("%d\n",find(0,r));
	return 0;
}