louisfghbvc的部落格

題目連結:  https://onlinejudge.org/external/119/11997.pdf

題目大意: 每行都取一個，找出k個最小和。

思路:  只需維護一個大小k的陣列就可。每次新的一排進來，先排序，並將第一個數字與原本的陣列全加總，放進priority_queue

這時pq大小為k，再來跟其他的陣列加總，但是如果暴力就變K^2。所以有個小技巧是如果每個值(第二小~第K小)加陣列(ans)比pq裡面的最大值還要小，則繼續pop，push。

反之停掉。

代碼: 

#include <bits/stdc++.h>
using namespace std;

int main()
{
    //freopen("out.txt", "w", stdout);
    int k;
    while(cin >> k){
        vector<int> pq(k, 0);
        for(int i = 0; i < k; ++i){
            cin >> pq[i];
        }
        sort(pq.begin(), pq.end());
        for(int i = 1; i < k; ++i){
            vector<int> arr(k, 0);
            for(int j = 0; j < k; ++j){
                cin >> arr[j];
            }
            sort(arr.begin(), arr.end());
            priority_queue<int> PQ;
            for(int j = 0; j < k; ++j){
                PQ.push(pq[j]+arr[0]);
            }
            for(int j = 0; j < k; ++j){
                for(int n = 1; n < k; ++n){
                    if(pq[j] + arr[n] < PQ.top()){
                        PQ.pop();
                        PQ.push(pq[j] + arr[n]);
                    }
                    else break;
                }
            }
            int j = k-1;
            while(!PQ.empty())
                pq[j--] = PQ.top(), PQ.pop();
        }
        bool f = 1;
        for(const auto &v : pq){
            if(!f) cout << " ";
            cout << v;
            f = 0;
        }
        cout << endl;
    }
    return 0;
}