题解 | #砝码Odw#

思路

二分大法好！！ 非正解，T了很多发，终于把他卡过去了。 看题解才知道可以将所有容器进制拆分直接塞，太妙了。 但所有人都在贪心的时候，就让我来一提供一份二分代码吧。

代码

#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<queue>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=1e5+7;
const int mod=1e9+7;

inline int read(){	int x=0;char ch=getchar();while(ch<'0'||ch>'9'){ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;}
void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}

int n,m,i,w[N],a[N];

inline bool check(int x){
	int res=0,fro;
	priority_queue<int>p,q;
	for(i=0;i<x;i++) q.push(a[i]);
	for(i=0;i<n;i++) p.push(w[i]);
	while(p.size()&&q.size()){
		fro=p.top();
		p.pop();
		if(fro>=q.top()){
			p.push(fro-q.top());
			++res;
			if(res>=x) return true;
		}
		q.pop();
	}
	return false;
}

void Solve(){
	n=read();m=read(); 
	for(i=0;i<n;i++) w[i]=read();
	for(i=0;i<m;i++) a[i]=read();
	stable_sort(a,a+m);
	int L=0,R=m+1,mid;
	while(R-L>1){
		mid=((L+R)>>1);
		if(check(mid)) L=mid;
		else R=mid;
	}
	write(L);
}

signed main(){
	int T=1;
	while(T--){
		Solve();
	}
	return 0;
}