题解 P1392 【取数】

· · 题解

我们考虑前面x-1行的前k小,升序放在b数组里

第x行共m个数,升序放在a数组里

然后只需要用大根堆维护,依次比较a[i]+b[j]的大小

在堆里已经有k个值的情况下,如果他比顶小就弹掉顶,把它丢进去

否则break掉,因为b数组单调不降,后面不可能有贡献

于是就做完了

但是真的做完了吗？这^{tm}不是3方1个log吗？？不会T的吗？？？

很多人想到这里就把这个做法ban了

然而再仔细想想:

考虑a[i]+b[j],由于a,b数组单调不降,必定有至少ij-1个元素小于等于他

所以当 k<ij 时循环一定会break掉

所以做一遍的循环次数不是看起来的平方

而是 \sum^{k}_{i=1} \frac{k}{i}

由调和级数或者写个代码算一遍可知其大概是k log_2 k

所以真实复杂度上限是2方2个log,而且根本跑不满

辅以fread在luogu拿下了暂时的rk1

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;++i)
using namespace std;
namespace IO{//这份代码拿来学fread也是很不错的
    const int Buffsize=1<<23;
    char c[Buffsize],*ch=c;
    void INIT(){fread(c,1,Buffsize,stdin);}
    int x,l;
    int read(){
        x=0,l=1;
        while(!isdigit(*ch)) {if ((*ch)=='-') l=-1; ch++;}
        while(isdigit(*ch)) x=x*10+(*ch^48),ch++;
        return x*l;
    }
}
using namespace IO;
priority_queue<int> q;
int a[805],b[805];
int main(){
    INIT(); int n=read(),m=read(),k=read(),o,oo;
    q.push(0); int op=800,ans=0;
    while(n--){
        For(j,1,m) a[j]=read(); sort(a+1,a+1+m);
        o=oo=0; while(!q.empty()) b[++o]=q.top(),q.pop();
        For(i,1,m)
            for(int j=o;j>=1;--j){//在这里b数组单调不升,所以倒着来
                if (oo<k) q.push(a[i]+b[j]),++oo;
                else if (q.top()<=a[i]+b[j]) break; //关键优化
                else q.pop(),q.push(a[i]+b[j]);
            }
    }
    o=0;
    while(!q.empty()) b[++o]=q.top(),q.pop();
    for(int i=o;i>=1;--i) printf("%d ",b[i]);
    return 0;
}