记录编号	124620	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2014] 采姑娘的小蘑菇	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	2.184 s
提交时间	2014-10-05 08:24:57	内存使用	2.49 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>

#define  maxn  100010
#define  maxm  100010

int n , m ;
long long waste = 0 , V = 0 ;
long long v[maxn] , w[maxm] , s[maxm] ;
int L = 1 , R , M , ret ;

/*bool Install(int t) {
	std::priority_queue<int>q ;
	for (i = 1 ; i <= n ; i ++ ) q.push(v[i]) ;
	for (i = t ; i > 0 ; i -- ) {
		if (q.empty()) return false ;
		tmp = q.top() ; q.pop() ;
		if (w[i] > tmp) return false ;
		else q.push(tmp-w[i]) ;
	}
	return true ;
}*/

bool dfs(int now , int lp , int x) {
	//now 从x->1枚举物品 x 代表要装前x个物品 
	int i , j , flag ;
	if (now == 0) return true ;
	//当将物品装完后返回 
	if (waste+s[x] > V) return false ;
	//s是物品质量的前缀和，
	//当已装装物品的容器的浪费空间+需物品的总质量>总容积时就不可能成功 
	if (now!=x && w[now]==w[now+1]) j = lp ;
	else j = 1 ;
	//如果当前物品now与上一个物品now+1质量相等
	//那么上一次搜索此质量时已经判断的不可能装下的容器们也不可能装下此物品
	//因为 1 =< w <= 128 ，那么质量相同的物品会比较多，这样减去了枚举数量 
	for (i = j ; i <= n ; i ++ ) {
		if (v[i] >= w[now]) {
			v[i] -= w[now] ;
			flag = false ;
			if (v[i] < w[1]) {
				flag = true ;
				waste += v[i] ;
				//w[1]是质量最小的物品，如果剩余的空间乘不下w[i],则剩余空间为浪费的空间 
			}
			if (dfs(now-1 , i , x)) {
				if (flag) waste -= v[i] ;
				v[i] += w[now] ;
				return true ;
			}
			if (flag) waste -= v[i] ;
			v[i] += w[now] ;
			//还原 
		}
	}
	return false ;
}

bool Install(int t) {
	waste = 0 ;
	if (dfs(t , 0 , t)) return true ;
	else return false ;
}

int Bsearch() {
	while (L <= R){
		M = (L+R)>>1 ;
		if (Install(M)) ret = M , L = M+1 ;
		else R = M-1 ;
	}
	return ret ;
}

int main() {
	#define  READ
	#ifdef   READ
		freopen("mushro.in" ,"r",stdin ) ;
		freopen("mushro.out","w",stdout) ;
	#endif
	scanf("%d%d", &n , &m ) ; int i ;
	for (i = 1 ; i <= n ; i ++ ) {
		scanf("%lld", &v[i] ) ; V += v[i] ;
	}
	R = m ; s[0] = 0 ;
	for (i = 1 ; i <= m ; i ++ ) scanf("%lld", &w[i] ) ;
	std::sort(v+1 , v+n+1) ;
	std::sort(w+1 , w+m+1) ;
	for (i = 1 ; i <= m ; i ++ ) s[i] = s[i-1]+w[i] ;
	printf("%d\n", Bsearch() ) ;
	return 0 ;
}