UVa 11997 K Smallest Sums

題意：
    有K行，每行有K個數字，從每行裡面各選出1個數字並加起來共有K^K種組合的和，輸出最小的K個和。

想法：
    我們可以先將第一行和第二行求出前K小的和，因此兩行數字就變成了一行數字，這一行數字再和第三行求出前K小的和，兩行又合併成一行，一直重複將兩行合併成一行，最後就是答案。
    因此現在關鍵是如何有效率求出兩行的數字前K個最小的和，如果暴力解的話為O(K^2)，很可能會TLE，用priority queue來解這題只要O(K)，過程如下：
*假設第一行數字陣列為L1，第二行數字陣列為L2，
*要丟進priority queue(底下簡稱PQ)裡的structure裡面含有兩個元素，第一個為val: 表示L1某個數+L2某個數的和，第二個為pos: 表示L2某個數在L2的位置(index)。

1. 將L1遞增排序
2. 將L2遞增排序。
3. 然後把L1裡面每個數字和L2[0]加起來，val=L1[i]+L2[0]和pos=0放到PQ裡面。
4. L1的數字就不會用到了
5. 之後每次從PQ裡面拿出第一個(最小的val)，將這個val放入L1(覆蓋以重複利用L1)，然後將這個val=(val-L2[pos]+L2[pos+1])和pos=pos+1丟回PQ裡
6. 重複步驟5 K次，L1裡面就有K個數字，表示這兩行已經合併成功
7. 讀入下一個L2，並重複步驟2~7，直到將K行合併成一行
8. 輸出L1

用這方法將兩行合併成一行的時候，只要做K次即可，因為我們已經將L1都丟進PQ裡面，然後每次都選最小和出來，並同時把可能的答案丟入PQ。