题目描述

给定 $M$ 个长度为 $N$ 的序列，从每个序列中各取一个数，可以构成 $M^N$ 个和。求这些和中前 $N$ 小的值。

解法

upd:评论区有人提醒我排序复杂度不可避，淦，我傻逼了，之前忘了。

注：由于这种效率较高的算法的代码、思维难度也较高，我给本题评出的难度为“困难”。

加强版：LOJ6254

本题为堆模拟搜索的绝佳练习题。蓝书上给出了一种主体部分为 $O(MN\log N)$ 的解法，现有题解使用的也全部是这种解法。但是，除无法避免的 $O(MN\log n)$ 的排序外，我们完全可以在 $O(N\log N)$ 的时间内解决这个问题。

在讨论本题的解法之前，让我们简单了解一种思想——堆模拟搜索。

该思想被广泛用于求解某种类型的前 $K$ 大 / 小方案，当使用这种思想解题时，算法复杂度一定为 $O(K\log N)$。其大致流程如下：

• 使用结构体表示搜索状态（类似动态规划与搜索算法的状态设计）。堆模拟搜索的状态设计有两个要点：
  • 状态记录全面且便于转移
  • 使用设计的状态进行转移时，可以使得转移过程不重不漏，即前 $K$ 次取出的状态一定是前 $K$ 优解
• 初始状态存至堆中。
• 取出堆顶状态，根据该状态扩展出其他可能会被计入答案的状态，令这些状态入堆。
• 重复以上流程 $K$ 次，得到的即为前 $K$ 优解。

相关练习题：[CQOI2016]伪光滑数

接下来，我们回到本题，用堆模拟搜索的思路，采取一种不同于蓝书做法的思考模式。为便于描述，下文中将第 $x$ 个序列中的第 $y$ 个数记作 $(x,y)$。

首先，最优解一定是将每个序列中最小的数（即从小到大排序后的第一个元素，下文默认所有序列已经进行排序）加起来。因此该方案即为堆中的初始状态。

下面思考状态的设计。考虑这样一种状态方案：用四元组 $(val,x,y,p=0/1)$ 代表一种状态，其中 $val$ 代表当前状态中 $M$ 个数的和，$x$ 代表我们人为地从前 $x$ 个序列中选出了一些数字，而第 $x+1$ 到第 $M$ 个序列中每个序列被选取的都是第一个数字。

此时，状态中值为 $0$ 或 $1$ 的 $p$ 看起来有些多余。事实上，该变量的值与我们采取的状态扩展策略有关。对于某个状态，我们有三种扩展方向：

• 当前状态中 $y<n$ ，在当前方案中去掉数字 $(x,y)$ 并替换为 $(x,y+1)$，得到一种新的状态 $(NewVal,x,y+1,0)$。
• 当前状态中 $x<m$，在当前方案中去掉数字 $(x+1,1)$ 并替换为 $(x+1,2)$，得到一种新的状态 $(NewVal,x+1,2,1)$。
• 当前状态中 $y=2$ 且由途径 2 或 3 转移得到，在当前方案中去掉 $(x,y)$，替换为 $(x,1)$，并选取 $(x+1,2)$，得到一种新的状态 $(NewVal,x+1,2,1)$。

由以上方案，我们不难看出，$p$ 代表的就是当前状态是否由途径 2 或 3 转移得到。该变量的设置是为了进行下一步的转移。

有些读者可能会感到不解——为什么只能通过这三种途径进行扩展？答案很简单，堆模拟搜索的扩展过程中，答案的转移必须遵循“不重不漏”的原则。通过这种转移方式，我们可以避免状态的重复扩展。

看起来剩下的工作已经很明显了——初始状态为 $(mintot,1,1,0)$，我们每次取出堆顶状态进行扩展，重复 $N$ 次即可。

但是请注意，在以上的扩展过程中，我们确实做到了“不重”，但却没有做到“不漏”。

为什么这么说呢？考虑这样三个序列：

10 100
15 50
20 30

如果直接按照上述方案进行转移，我们会漏下一种方案，即选取 $10$、$15$ 与 $30$。造成这一点的原因是，我们首先扩展出了选取 $10$、$50$ 与 $20$ 的状态。

为了解决这个问题，我们需要进行一种操作——在进行第一次扩展前，将每个序列以“次小值减去最小值”作为关键字从小到大进行排序。这一步操作的目的是为了保证我们在进行扩展时先扩展出能令新方案的元素和较当前方案增量较小的方案。接下来，我们就可以进行转移了。

至此，本题得到完美解决。经实际测试验证这份代码耗时远少于所有其他题解。

C++ 代码（直接改编自 LOJ6254）

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int p[1010],n,m,nt,t;
long long tot;
vector<int>vec[1010];
struct asdf{
    long long val;
    int x,y;
    bool p;
    asdf(){}
    asdf(long long vall,int xe,int yo,bool pp){val=vall;x=xe;y=yo;p=pp;}
    bool operator <(const asdf &b)const{return val>b.val;}
};
priority_queue<asdf>q;
int read(){
    char ch=getchar();int nn=0,ssss=1;
    while(ch>'9'||ch<'0'){if(ch=='-')ssss*=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
    return nn*ssss;
}
bool SWriteFaster(long long x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)SWriteFaster(x/10);
    putchar(x%10+'0');
    return true;
}
bool cmp2(int a,int b){return vec[a][1]-vec[a][0]<vec[b][1]-vec[b][0];}
bool solve(){
    tot=0;
    while(!q.empty())q.pop();
    m=read();n=read();nt=n;
    for(int i=1;i<=m;i++){
        vec[i].clear();
        for(int j=1;j<=n;j++)
            vec[i].push_back(read());
        sort(vec[i].begin(),vec[i].end());
        p[i]=i;
        tot+=vec[i][0];
    }
    sort(p+1,p+m+1,cmp2);
    q.push(asdf(tot,1,0,false));
    while(nt--){
        asdf np=q.top();q.pop();
        SWriteFaster(np.val);putchar(' ');
        if(np.y+1<n)q.push(asdf(np.val-vec[p[np.x]][np.y]+vec[p[np.x]][np.y+1],np.x,np.y+1,false));
        if(np.x<m)q.push(asdf(np.val-vec[p[np.x+1]][0]+vec[p[np.x+1]][1],np.x+1,1,true));
        if(np.x<m&&np.p)q.push(asdf(np.val-vec[p[np.x]][np.y]+vec[p[np.x]][0]-vec[p[np.x+1]][0]+vec[p[np.x+1]][1],np.x+1,1,true));
    }
    putchar('\n');
    return true;
}
int main(){
    t=read();
    while(t--)solve(); 
}