首页 > 代码库 > UVA 11997 【K Smallest Sums】
UVA 11997 【K Smallest Sums】
【题意分析】
本题目是要求总和最小的k个值，当然我们没有必要把所有的值全部求一次，我们首先应该对每组元素进行排序。然后根据两两合并的观点节约空间（先把前两组数据合并为一组数据，最后把下面的每一组数据和之前合并所得的那组数据进行合并）。那么最后剩下的那组数据中的前k个数字就是最小的数字。
【借鉴之处】
本题采用的两两合并的观点很新颖，值得学习理解。
【AC代码】
#include<iostream>#include<queue>#include<algorithm>using namespace std;struct Item{ int s,b; Item(int s,int b):s(s),b(b){} bool operator <(const Item &a) const{ return s>a.s; }} ;void merge(int *A,int *B,int *C,int n){ priority_queue<Item>q; for(int i=0;i<n;i++) q.push(Item(A[i]+B[0],0)); for(int i=0;i<n;i++) { Item item =q.top();q.pop(); int b=item.b; C[i]=item.s; if(b+1<n) q.push(Item(item.s-B[b]+B[b+1],b+1));//细细体会此处 }}const int maxn=768;int A[maxn][maxn];int main(){ int n; while(scanf("%d",&n)==1) { 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++) { merge(A[0],A[i],A[0],n); } printf("%d",A[0][0]]); for(int i=1;i<n;i++) printf(" %d",A[0][i]); printf("\n"); } return 0;}
UVA 11997 【K Smallest Sums】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。