網頁

2014年3月7日 星期五

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。


1 則留言: