图片加载可能有点慢，请跳过题面先看题解，谢谢
我们先考虑两个序列的情况（以下这一段蒯自 刘汝佳训练指南）：
这个问题可以转换成一个多路归并问题，有这样一个含有 \(n^2\) 个元素的表：- \(A[1]+B[1]\leq A[1]+B[2]\leq A[1]+B[3]\leq\) ...
- \(A[2]+B[1]\leq A[2]+B[2]\leq A[2]+B[3]\leq\) ...
- \(A[3]+B[1]\leq A[3]+B[2]\leq A[3]+B[3]\leq\) ...
- ......
这里用优先队列维护一个二元组 \((s,b)\) ，其中，\(s=A[a]+B[b]\)，\(s\) 最小的放堆顶
每次从堆中取出一个 \((s,b)\) 后，将 \((s',b+1)\) 丢入堆中，直到取出了 \(n\) 个最小值 但是我们在维护 \((s,b)\) 这个二元组时并没有记录 \(a\) 的值，那则么样才能得到 \((s',b+1)\) 呢 很简单， \(s'=s-B[b]+B[b+1]\)，根本不需要知道 \(a\) 。 $ $ 这道题将上面那个两个序列的情况进行了推广 其实就相当于每次拿一个序列去跟 \(A序列\) 进行上面那个操作，然后用答案覆盖 \(A\)，直到所有序列都操作过一次//made by Hero_of_Someone#include#include #include #include #include #define il inline#define RG registerusing namespace std;il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar(); if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }int n,a[1010][1010];struct node{int s,x; il bool operator<(const node &c)const{return s>c.s;}};priority_queue q;il void init(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) a[i][j]=gi(); sort(a[i]+1,a[i]+n+1); }}il void work(){ for(int i=2;i<=n;i++){ for(int j=1;j<=n;j++) q.push((node){a[1][j]+a[i][1],1}); for(int j=1;j<=n;j++){ node x=q.top(); q.pop(); a[1][j]=x.s; int b=x.x; if(b