自动搬运

查看原文

来自洛谷，原作者为

	wjy666 **

搬运于2025-08-24 21:24:34，当前版本为作者最后更新于2018-12-20 17:58:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们考虑前面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;
}