首页 > 代码库 > UVA 11997 The K smallest Sums
UVA 11997 The K smallest Sums
给出K*K的矩阵,每一行取一个数,构成K个数的和,总共有 k^k种可能,从中取出前k个最小的。
一开始犯了错,因为只要对每行排序,最小的必定是第一列的和,然后我当时就想着,逐步推进,每次将某行的那个数变成其下一列那个数,当然间距要最小。我这样明显是不对的,这样的话每个数只用了一次,而题目的意思明显是可以重复多次。
然后大白上说的是把他看成两行,即每次处理两行,留下最小的k个 再与下一次读入的那一行继续处理。这个方法相当给力,不过有个难点是,怎么在两行的时候,比较快的得到前k小的,我试过全部算一遍, k^k种情况。。会超时。。之后想了很久 都没想出一个比较有效的方法,后来看到一种很叼的方法,而且很容易证明,即 先把
排完序后的 第一行的 A【0】 到 A【K-1】 分别和 第二行的B【0】组成 最早的k个数,目前只知道A【0】+B【0】是最小的,其余的还不确定,但是我可以确定的是,第二小的,一定是A【0】+B【1】或者上述k-1个数中的某一个,也就是说,我把这些数,放入优先队列里面,然后每次pop出最小的数,输出,然后把刚刚最小的数的下一个又push进队列里面,则下一个pop出来的 必定是第二小的。。。这样的话 这样 重复k次,便能得到 前k小的数
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;struct node{ int s,b; bool operator < (const node& rhs) const{ return s>rhs.s; }};priority_queue<node> q;const int N=800;int n;int A[N];int B[N];void solve(){ while (!q.empty()) q.pop(); for (int i=0;i<n;i++){ q.push((node){A[i]+B[0],0}); } int cnt=0; while (cnt<n){ node tmp=q.top(); q.pop(); A[cnt++]=tmp.s; q.push((node){tmp.s-B[tmp.b]+B[tmp.b+1],tmp.b+1}); }}int main(){ while (scanf("%d",&n)!=EOF) { while (!q.empty()) q.pop(); for (int i=0;i<n;i++){ scanf("%d",&A[i]); } for (int i=1;i<n;i++){ for (int j=0;j<n;j++){ scanf("%d",&B[j]); } sort(B,B+n); solve(); } printf("%d",A[0]); for (int i=1;i<n;i++){ printf(" %d",A[i]); } puts(""); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。