首页 > 代码库 > uva 11997 K Smallest Sums
uva 11997 K Smallest Sums
首先对每行进行排序，并对与前两行有$A = a_1 \leq a_2 \leq \cdots \leq a_k$和$B = b_1 \leq b_2 \leq \cdots \leq b_k$。首先把所有的$b_i , i\in [1,k]$与$a_1$进行求和，并加入优先队列中。其中最小的必然是$a_1+b_1$，在优先队列队首。然后只需在优先队列中压入$a_1+b_2$，没有压入$a_2+b_1$原因是该和已经在队列中存在了，没有压入$a_2+b_2$的原因是$a_2+b_2 \leq a_1 + b_2$因此无需压入。
从而循环往复，对所有的k行都进行上面的操作。即可取出最小的k个和。
代码如下：
1 #include <iostream> 2 #include <queue> 3 #include <string> 4 #include <cstdio> 5 #include <algorithm> 6 using namespace std; 7 int arr[800][800]; 8 int k; 9 class node10 {11 public:12 int num, sum;13 node(int n, int s)14 {15 num = n;16 sum = s;17 }18 bool operator < (const node & n)const19 {20 return sum > n.sum;21 }22 23 };24 void merge(int *a, int *b, int *res, int k)25 {26 priority_queue<node> q; 27 28 node tmp(0,0);29 for( int i = 0 ; i < k ; i++ )30 {31 tmp.sum = a[i] + b[0];32 tmp.num = 0;33 q.push(tmp);34 }35 for( int i = 0 ; i < k ; i++ )36 {37 tmp = q.top();38 res[i] = q.top().sum;39 q.pop();40 if(tmp.num + 1 < k) 41 { 42 tmp.sum = tmp.sum - b[tmp.num] + b[tmp.num+1]; 43 tmp.num++; 44 q.push(tmp); 45 } 46 }47 }48 int main(int argc, char *argv[])49 {50 while( scanf("%d", &k ) != EOF)51 {52 for( int i = 0 ; i < k ; i++ )53 {54 for( int j = 0 ; j < k ; j++ )55 {56 scanf("%d", &arr[i][j]);57 }58 sort(arr[i], arr[i]+k);59 }60 for(int i = 1 ; i < k ; i++ )61 merge(arr[0], arr[i], arr[0], k);62 for(int i = 0 ; i < k ; i++ )63 printf("%d%s",arr[0][i],i != k-1?" ":"\n");64 }65 }
uva 11997 K Smallest Sums
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。