K Smallest Sums

uva11997:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=3148&mosmsg=Submission+received+with+ID+13942033

题意:给你k个数组,每个数组里有k个数,然后每个数组里面取出一个数相加会得到一个数,让你求出最小的看的数。

题解:白书的分析:

分析:这题有简化版本的,即2个整数数组A,B,包含K个元素,在每个数组中取一个元素加起来,可以得到k^2个和,求这些和中最小的K个值。

我们需要把这k^2个和组织成如下k个有序表.

表1:A1+B1<=A1+B2<=......<=A1+Bk

表2: A2+B1<=A2+B2<=......<=A2+Bk

表k:Ak+B1<=AK+B2<=......<=Ak+Bk

我们可以用二元组(s,b)来表示一个元素即s=Aa+Bb;为什么不保存A的下标a呢?因为我们用不到a的值。如果我们需要元素(s,b)在表a的下一个元素(s',b+1).只需要计算s'=s+B[b+1]-B[b];

思想感觉就是DP。

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int a[][];
int k;
int ans[];
struct Node{
int s;
int id;
bool operator<(const Node a)const {
return s>a.s;
}
};
void merge(int a[],int b[]){
priority_queue<Node>Q;
for(int i=;i<=k;i++){
Node tt;
tt.s=a[i]+b[];
tt.id=;
Q.push(tt);
}
for(int i=;i<=k;i++){
Node temp=Q.top();
Q.pop();
ans[i]=temp.s;
Node t2;
int num=temp.id;
if(num<k){
t2.s=temp.s-b[num]+b[num+];
t2.id=num+;
Q.push(t2);
}
}
}
int main(){
while(~scanf("%d",&k)){
memset(a,,sizeof(a));
memset(ans,,sizeof(ans));
for(int i=;i<=k;i++){
for(int j=;j<=k;j++)
scanf("%d",&a[i][j]);
sort(a[i]+,a[i]+k+);
}
merge(a[],a[]);
for(int i=;i<=k;i++)
merge(ans,a[i]);
for(int i=;i<k;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[k]);
}
}
上一篇:使用DBUnit框架数据库插入特殊字符失败的查错经历


下一篇:在Centos下面FTP映射方案