bzoj 1110: [POI2007]砝码Odw

题解

先说一个简单的做法：
因为都是倍数关系，可以发现，二分答案以后，每个数能放就放就一定是最优的，因为不会出现说什么大的放了以后小的放不下的情况
这个的话可以用堆维护一个最大值
这样是$lo{g}^2$的，并且使用了堆，在bzoj上过不去
可以发现，因为我们是能放就放，因此，并不需要二分答案
大往小扫下去，放不下了就把最大的空间释放出来，这样就不可以用堆了，要用一个set维护，时间复杂度是$O(nlogn)$了，常数虽然从堆变成了set，但是怎么说复杂度也变低了
但其实还有常数较小的$lo{g}^2$的做法，参见$Claris$的博客，因为没有使用任何数据结构，于是在bzoj上也可以通过
然后我又测了一下，发现二分答案套堆的做法，加个读优也可以卡过
那我写一个log干什么，囧

再说一下题解的高妙做法
算了，不写了，参见CQzhangyu吧
似乎还是太懒了

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
using namespace std;
typedef long long LL;
const int N=100005;
int n,m;
int a[N],b[N];
struct qt	{
    int x;};
bool operator < (qt x,qt y)	{
    return a[x.x]==a[y.x]?x.x<y.x:a[x.x]>a[y.x];}
set<qt> s;
int bel[N];
int read ()
{
    char ch=getchar();int x=0;while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x;
}
int main()
{
    n=read();m=read();for (int u=1;u<=n;u++) a[u]=read();for (int u=1;u<=m;u++) b[u]=read();sort(b+1,b+1+m);for (int u=1;u<=n;u++) s.insert((qt){
    u});int R=0;int t=(*s.begin()).x;for (int u=m;u>=1;u--){
    if (b[u]<=a[t]){
    R=u;s.erase((qt){
    t});bel[u]=t;a[t]-=b[u];// printf("%d %d\n",t,a[t]);s.insert((qt){
    t});break;}}
// printf("%d\n",R);for (int u=R-1;u>=1;u--){
    int t=(*s.begin()).x;// printf("%d %d %d %d\n",t,u,a[t],b[u]);if (b[u]>a[t]){
    s.erase((qt){
    bel[R]});a[bel[R]]+=b[R];s.insert((qt){
    bel[R]});R--;t=(*s.begin()).x;}s.erase((qt){
    t});bel[u]=t;a[t]-=b[u];s.insert((qt){
    t});}printf("%d\n",R);return 0;
}