先讨论两个序列a,b
$a_1,a_2,a_3,……,a_n$
$b_1,b_2,b_3,……,b_n$
那么我们可以得到$n ^ 2$个和
$a_1+b_1,a_1+b_2,a_1+b_3,……,a_1+b_n$
$a_2+b_1,a_2+b_2,a_2+b_3,……,a_2+b_n$
……………………………………………………
$a_n+b_1,a_n+b_2,a_n+b_3,……,a_n+b_n$
我们发现按原始顺序的话
n个最小和是乱掉的
那么我们就需要从小到大排序 使得$a_1$为最小
那么现在的答案就显然是第一列
$a_1+b_1,a_1+b_2,a_1+b_3,……,a_1+b_n$
好的 那么我们只要进行$m - 1$次
就能得到题目需要的最小的 n 个序列和
对于一个$a_1+b_1$弹出后如何插入$a_2+b_1$
答案显然
在队列里记录一个idx对应a的下标
那么$c_2 = c_1 - a_1 + a_2 $
应该都会了吧
Author:Miku_𝓜𝓪𝓼𝓽𝓮𝓻
Date:2021/5/29
#include <bits/stdc++.h>
using namespace std;
typedef long long LL ;
typedef pair<int,int> pii ;
int read() {
int x = 0 ; bool f = false ; char ch = getchar() ;
for (;!isdigit(ch);ch = getchar()) f |= (ch == '-') ;
for (;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48) ;
return f ? ~ x + 1 : x ;
}
const int N = 2e3 + 5 ;
int T , n , m , idx ;
int arr[N] , seq[N] , ans[N] ;
void solve() {
priority_queue<pii,vector<pii>,greater<pii> > Q ;
for (int i = 1 ; i <= n ; ++i ) Q.push(make_pair(arr[1] + seq[i],1)) ;
for (int i = 1 ; i <= n ; ++i ) {
pii x = Q.top() ; Q.pop() ;
ans[i] = x.first , idx = x.second ;
Q.push(make_pair(x.first - arr[idx] + arr[idx + 1],idx + 1)) ;
}
memcpy(arr,ans,sizeof ans) ;
}
signed main() {
T = read() ;
while (T --) {
m = read() , n = read() ;
for (int i = 1 ; i <= n ; ++i ) arr[i] = read() ;
sort(arr + 1,arr + 1 + n) ;
for (int i = 1 ; i < m ; ++i ) {
for (int j = 1 ; j <= n ; ++j )
seq[j] = read() ;
solve() ;
}
for (int i = 1 ; i <= n ; ++i )
printf("%d%c",arr[i],i == n ? '\n' : ' ') ;
} return 0 ;
}
tql
%%%