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;

}

巴特西

UVA 11997 The K smallest Sums

最新文章

热门文章