Kattis - Synchronizing Lists

題目

https://open.kattis.com/problems/synchronizinglists

給定兩個序列，$A$, $B$，題目希望我們能將序列 $B$ 排序，使得 $B$ 的元素排列順序和 $A$ 是相同的

輸入包含少於 100 筆測試資料，每筆資料包含一個正整數 $n$

接下來會有 $2n$ 行，前 $n$ 行表示序列 $A$ 的元素，後 $n$ 行表示序列 $B$ 的元素

輸出排列順序與 $A$ 相同的新序列 $B’$

$1 \leq n \leq 5000 \quad -10000 \leq \texttt{每個元素的值} \leq 10000$

想法

要知道 $B$ 序列應該要怎麼排序，就必須要先知道 $A$ 序列是怎麼排序的

但是如果我們已經知道序列 $A$ 的每個元素應該分別要對應到序列 $B$ 的哪個元素，那我們就找到 $B’$ 了

舉例來說: $A = (48, 10, 97) \quad B = (7, 46, 20)$

如果我們已經先知道 $10 \rightarrow 7 \quad 48 \rightarrow 20 \quad 97 \rightarrow 46$

那麼我們的答案 $B’$ 就顯而易見了 $B’ = (7, 20, 46)$

要找到 $A$ 的每個元素要對應到 $B$ 的哪個元素是很容易的

我們只要將 $A, B$ 分別由小到大排序，相對應位置上的元素就是了

最後再對應回原本的序列 $A$ 就有 $B’$ 了

詳細來說，我們的步驟會是這樣:

1. 輸入
2. 將序列 $A$ 複製一份叫做 $A’$
3. 將 $A’$ 以及 $B$ 由小到大排序
4. 製作一份表格，將每個 $A$ 的元素對應到 $B$ 的元素
5. 按照 $A$ 的順序，輸出新序列 $B’$

Code

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	// tmp 是複製 fir 陣列用
	// tbl 陣列是對應用的表格
	int n, fir[5005], sec[5005], tmp[5005], tbl[20010];
	bool out=false;
	while(cin>>n){
		if(out) cout<<"\n";
		else out=true;
		
		for(int i=0 ; i<n ; i++){
			cin>>fir[i];
			tmp[i] = fir[i];
		}
		for(int i=0 ; i<n ; i++){
			cin>>sec[i];
		}
		sort(tmp, tmp+n);
		sort(sec, sec+n);
		for(int i=0 ; i<n ; i++){
			// 因為數值範圍包含負數，所以統一加上 10000 避免負數
			tbl[tmp[i]+10000] = sec[i];
		}
		for(int i=0 ; i<n ; i++){
			// 記得要將 10000 加上去
			cout<<tbl[fir[i]+10000]<<"\n";
		}
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(n)$

每筆測資排序時間複雜度為 $O(nlogn)$

每筆測資輸出時間複雜度為 $O(n)$

每筆測資總時間複雜度約為 $O(n + nlogn)$