2011年3月15日 星期二

UVa 482 Permutation Arrays

解題策略

題目要求依照第一個陣列的值來排列第二個陣列,照著直覺來寫並不困難。
不過我這兒要提另一個比較狡猾的做法。首先我把第一個陣列叫作pos,pos是一個位置的對應表,告訴你元素排列的新位置。比方說 pos[5] = 3 意思是原本陣列第五個元素應該要移到位置三去。

假如我們翻轉陣列 pos 的 key 與 value,例如把 pos[5] = 3 變成了 pos'[3] = 5,意義上沒有變化: 位置三應該擺放未排列前的舊陣列的第五個元素,但是對程式來說就很方便了,因為我們可以直接依據pos'輸出新陣列,而不需要先經過排序:
for(int i=0;i<len;++i){
    cout << data[ pos[i] ] <<'\n';
}

好了,那現在問題就是題目給的測資是pos,我們該怎麼產生這個key/value翻轉的 pos' 對應表呢 ?
int index=0;
int x;
while( cin>>x ) {
    pos[x-1] = index; //index shift
    index++;

    if( cin.get()=='\n')
        break;
}
其中一個好辦法是把key/value翻轉過來讀取,原本的pos[index] = x 變成 pos[x] = index;。那個x-1是因為題目給的測資是1起算,而C語言陣列是0起算。一旦 pos' 建好,資料讀取完畢後就能直接輸出結果了,中間省去一道排序的工作。

注意

雖然題目說第二個陣列是浮點數陣列,但是最好當成字串來處理,省得應付格式麻煩。範例測資 :
------Input------
2

3 1 2
32.0 54.7 -2

1 3 2 4
.004 +5.0e0 0.000007  3
------Output------
54.7
-2
32.0

.004
0.000007
+5.0e0
3
本題讀取時有許多空行,輸出時也要求每個case「之間」要有空行,要小心處理這些空行。

碎碎念

原本我第一次也是乖乖排序,後來在網上看見這招手法,想說非學起來不可。