题解：P2409 Y的积木
Circle_Table
·
·
题解
这边是题目传送门喵！
欢迎到博客园阅读！
题意简述
## 思路
先考虑最暴力的方法：枚举所有情况，然后取最小值。复杂度 $\Theta(m^n)$。
考虑优化。想到了[序列合并](https://www.luogu.com.cn/problem/P1631)这一题，其实两者有共通之处。当 $n=2$ 时其实就几乎是一个题了。如果两行的数量不一样和选出前 $k$，在原题基础上其实很好修改。
对于两行，我们存储可能进入前 $k$ 的和加入优先队列，然后取优先队列中最小的 $k$ 个作为真正的前 $k$ 即可。假设一行是 $a$，一行是 $b$，目前的和为 $x=a_i+b_j$，则一定比它小的和有 $j\times(i-1)+j-1$ 个（理由是：前 $i-1$ 行一定有 $j\times(i-1)$ 个小于 $x$，而本行一定有 $j-1$ 个小于 $x$），则在最优情况下其排名为 $j\times(i-1)+j$，当这个数不超过 $k$ 即可能进入前 $k$。
以上步骤复杂度我也不知道，但大致是 $\Theta(k \log k)$。于是做完了 $n=2$ 的情况，接下来推广到一般。
不难发现，如果在我选到第 $i$ 行时，某种选法就已经不是前 $k$ 了，那无论如何在后面都无法重新进入前 $k$（这是显然的，后面每一个盒子都选最小值即可）。
同时发现当 $m>k$ 时只有前 $k$ 个产生贡献。我们用一个数组 $f$ 存储 $1\sim i-1$ 行的前 $k$。对于每一个 $i\geq 2$，都将 $1\sim i-1$ 行的前 $k$ 视为一行，第 $i$ 行视为另一行。对这两行做一遍上面 $n=2$ 的操作，然后将得出来的新的前 $k$ 覆盖到 $f$ 数组上。
最后一次操作完得到的 $f$ 数组就是答案。
## 代码
细节问题：
1. 为了实现方便，对照[序列合并](https://www.luogu.com.cn/problem/P1631)一题的格式，将两行的个数都默认为 $k$，将不存在的位置设置为 $+\infty$。
2. 记得每一行处理完之后要清空优先队列。
```cpp
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);i<=(int)(b);i++)
using namespace std;
const int N=1e4+5;
const int inf=0x3f3f3f3f;
int n,m,k,a[N],f[N];
priority_queue<int,vector<int>,greater<int> >q;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
loop(t,1,n){
cin>>m;
loop(i,1,m)cin>>a[i];
loop(i,m+1,k)a[i]=inf;
sort(a+1,a+1+m);
if(t==1){
loop(j,1,k)f[j]=a[j];
continue;
}
loop(i,1,min(m,k)){
for(int j=1;j*(i-1)+j<=k;j++)q.push(a[i]+f[j]);
}
loop(i,1,k)f[i]=q.top(),q.pop();
while(!q.empty())q.pop();
}
loop(i,1,k)cout<<f[i]<<' ';
return 0;
}
```
完结撒花花喵~