思路
二分大法好!! 非正解,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;
}