uva 11997 K Smallest Sums

本文从WordPress迁移而来, 查看全部WordPress迁移文章

归并思想 + 优先队列

题意:给一个k*k的矩阵,只能从每一行中选出一个值,然后k个值相加的到一个和,现在从最小和开始输出前k个最小和。

这题需要用到一种归并的思想,首相考虑只有2行的情况,对每一行进行升序排序

a1,a2,a3,a4……….ak

b1,b2,b3,b4……….bk

先将a1+b1,a2+b1,a3+b1,a4+b1,a5+b1……ak+b1,这k个和放进一个优先队列里,这k个和并不一定是前k个最小和,而是,前k个最小和甚至前多少个和都好,一定能由这k个和诱导出来,怎么诱导往下看。在优先队列中取出最小值,这个肯定是最小和(a1+b1),然后把a1+b2放进去,这时候可以保证次小和一定在队中,虽然这个结论是比较显然的,但还是简要说明一下。

不在队中的元素,a1+b3,a1+b4,a1+b5…….a1+bk,可知这些值都肯定比a1+b2大,它们都不可能是次小和,而a1+b2在队中

不在队中的元素,a2+b2,a2+b3,a2+b4…….a2+bk,可知这些值都肯定比a2+b1大,它们都不可能是次小和,而a2+b1在队中

……………………………..

不在队中的元素,ak+b2,ak+b3,ak+b4…….ak+bk,可知这些值都肯定比ak+b1大,它们都不可能是次小和,而ak+b1在队中

这时候再在队中取出最小元素,就必定是次小和,如果取出来的元素是a1+b2,那么就放进a1+b3;如果取出a2+b1,那么就放进a2+b2,这样也同样可以保证第3小和一定在队中。
也就是说没有入队的元素全部比队中的元素小(可知这个性质是时刻保持的),那么第i次在队中找出最小值,就一定是第i小和

所以看到,诱导的根据就是每次取出的是ai+bj的时候,就把ai+bj+1放进去,所以我们需要记录每个和有ai,bj组成的,需要i,j下标,但是发现诱导的时候,其实只改变b的下标,那么可以把a下标省掉

一开始把<sum,j>放进去,取出来的时候,计算要放进去的和就是 S = sum + b[j+1] - b[j],a不影响结果,然后把<S,j+1>放进去

考虑了2行的来考虑3行,假设2行产生的k k个和都被算出来,我们把它排好,第3行也排好序
s1,s2,s3,s4…sk
k

c1,c2,c3….ck

由于我们最后只需要前k个和,所以上面的s其实只需要前k个就可以,就算的到后面的也让没用

比如加入sk+1,这个值与c可以产生k个和c1+sk+1,c2+sk+1,c3+sk+1,c4+sk+1…….ck+sk+1

可知这些数字肯定不是前k个最小和,因为c1+sk,c1+sk-1,c1+sk-2…..c1+s1 肯定都比上面的小,更不用说还有其他的了

所以只剩下了

s1,s2,s3,s4……….sk

c1,c2,c3,c4……….ck

这和上面的a,b是一样的道理,用上面的方法即可

这就是本题的归并思想,因为这个问题,一行顺着一行下来处理,并不会改变问题本质,原因在于它只需要找出前k个最小和

如果前面m行内计算出很多和,k个后面的都是可以抛弃的,因为在下1行相同的情况的,怎么加都不比前k个小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define N 800

int n,a[N][N];
struct elem{
int val,index;
elem(int x,int y){
val = x; index = y;
}
bool operator<(const struct elem &a)const{
return val > a.val;
}
};
priority_queue<elem>que;

void Mer(int *p,int *q){
while(!que.empty())que.pop();
for(int i = 0; i < n ; i++)
que.push(elem(p[i]+q[0],0));
for(int i = 0; i < n; i++){
elem temp = que.top();
que.pop();
p[i] = temp.val;
int index = temp.index;
que.push(elem(temp.val + q[index+1]-q[index] , index+1));
}
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 0; i < n; i++){
for(int j = 0; j < n ; j++)
scanf("%d",&a[i][j]);
sort(a[i],a[i]+n);
}
for(int i = 1; i < n ;i++){
Mer(a[0],a[i]);
}
for(int i = 0; i < n - 1; i++)
printf("%d ",a[0][i]);
printf("%d\n",a[0][n-1]);
}
return 0;
}