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

碎碎念

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

	/**
	* UVa 482 Permutation Arrays
	* Author: chchwy
	* Last Modified: 2011/03/15
	* Blog: http://chchwy.blogspot.com
	*/
	#include<iostream>
	#include<cstdio>
	#include<string>
	#include<vector>
	using namespace std;
	enum { MAX = 1000 };
	int pos[MAX];
	string data[MAX];
	int read_pos_array()
	{
	int x, index = 0;
	while ( cin >> x )
	{
	pos[x - 1] = index; //index shift (between 0 start and 1 start)
	index++;
	if ( cin.get() == '\n')
	break;
	}
	return index;
	}
	void read_data_array(int len)
	{
	for (int i = 0; i < len; ++i)
	{
	cin >> data[i];
	}
	cin.ignore(128, '\n');
	}
	int main()
	{
	#ifndef ONLINE_JUDGE
	freopen("482.in", "r", stdin);
	#endif
	int num_case;
	cin >> num_case;
	while (num_case--)
	{
	cin.ignore(128, '\n');
	int len = read_pos_array();
	read_data_array(len);
	for (int i = 0; i < len; ++i)
	{
	cout << data[ pos[i] ] << '\n';
	}
	if (num_case != 0)
	putchar('\n');
	}
	return 0;
	}

view raw 482.cpp hosted with ❤ by GitHub