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「之間」要有空行，要小心處理這些空行。

碎碎念

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