# 演算法課程題解 - 排序總和挑戰
# 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$
## 想法 By Koios
要知道 $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'$
### 程式碼
```cpp=
//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)$
# UVa 156
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?156
定義一個字串是 anagrams ，如果這個字串的任何排列方式除了本身以外都不是一個存在的單詞，我們就稱這個字串是 anagrams
現在給你很多的字串，這些字串組成了字典，問在這本字典當中有哪些字串是 anagrams
注意，在判斷 anagrams 時不需要理會大小寫
但是輸出時需要理會大小寫，並且依照字典序排序
## 想法 By Koios
如果說字串 $A$ 經過排列後可以形成字串 $B$，那麼字串 $A, B$ 分別經過排序之後得到的 $A', B'$ 也就會相等
依照這樣的性質，我們建立一個新的結構(struct)，紀錄字典當中每個字轉成小寫並且經過排序後的樣子、以及原字串在字典當中的編號
那麼這個新的結構所組成的新字串陣列在經過排序之後，根據上面所得到的性質我們會發現，那些排列後相同的字串都會被排在一起
接下來我們只要篩掉這些字串，把剩餘的字串再透過編號對應回原本的字串，我們就拿到還沒排序過的答案了
最後經過排序就是正解
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
struct words{
string word;
int id;
};
int i=0, l=0;
string input, dict[1005], output[1005];
words word[1005];
bool cmp(words p, words q){
if(p.word.compare(q.word)!=0) return p.word < q.word;
return false;
}
int main(){
while(cin>>input && input.compare("#")!=0){
// 字典先存放一份原始檔
dict[i] = input;
// 都先轉換成小寫
for(int j=0 ; j<input.size() ; j++){
input[j] = tolower(input[j]);
}
// 接者把字串排序好
sort(input.begin(), input.end());
//放進新的結構當中
word[i].word = input;
word[i].id = i;
i++;
}
// 把新的結構所形成的陣列排序
sort(word, word+i, cmp);
for(int j=0, k ; j<i ; ){
for(k=j ; k<i ; k++){
if(word[j].word.compare(word[k].word)!= 0) break;
}
if(k - j == 1){
// 是 anagrams
output[l++] = dict[word[j].id];
j++;
}
else{
// 不是 anagrams
j = k;
}
}
// 輸出結果要排序
sort(output, output+l);
for(int j=0 ; j<l ; j++){
cout<<output[j]<<"\n";
}
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度 $O(n)$，$1 \leq n \leq 1000$
假設每個單詞的長度為 $s_i$， $S = \sum_{i = 0}^{n-1}s_i$
建立新陣列的時間複雜度為 $O(S + \sum_{i = 0}^{n-1}s_ilog{s_i})$
排序新陣列的時間複雜度為 $O(nlogn)$
篩選的時間複雜度為 $O(n)$
輸出結果排序時間複雜度約為 $O(nlogn)$
輸出時間複雜度約為 $O(n)$
總時間複雜度約為 $O(3n + nlogn + S + \sum_{i = 0}^{n-1}s_ilog{s_i})$
# UVa 11462
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11462
有多筆測試資料，每筆測試資料第一行有一個正整數 $n$，接下來有 $n$ 個數字
這 $n$ 個數字保證都在 $1$ ~ $100$ 之間
請將這些數字排序後輸出
## 想法 By Koios
最單純的想法就是直接排序後輸出
可以直接使用 C++ STL sort
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, arr[2000010];
int main(){
while(cin>>n && n){
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n);
for(int i=0 ; i<n ; i++){
if(i) cout<<" ";
cout<<arr[i];
}
cout<<"\n";
}
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度為 $O(n)$
排序時間複雜度為 $O(nlogn)$
輸出時間複雜度為 $O(n)$
總時間複雜度約為 $O(2n + nlogn)$
## 想法 2
因為已知數字的範圍，而且範圍不大
我們可以直接使用陣列紀錄每個數字出現的次數，再統計過後輸出即可，甚至不需要排序
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, arr[2000010], age[110];
bool out=false;
int main(){
while(cin>>n && n){
// 先初始化 age 陣列
for(int i=0 ; i<=100 ; i++){
age[i]=0;
}
for(int i=0 ; i<n ; i++){
cin>>arr[i];
// 統計
age[arr[i]]++;
}
for(int i=1 ; i<=100 ; i++){
if(age[i] > 0){
for(int j=0 ; j<age[i] ; j++){
if(out) cout<<" ";
else out=true;
cout<<i;
}
}
}
cout<<"\n";
}
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度為 $O(n)$
統計時間複雜度為 $O(n)$
輸出時間複雜度為 $O(n)$
總時間複雜度約為 $O(3n)$
# UVa 468
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?468
我們今天設計了一個新的加密方式，首先是先寫下明文 $P$
接下來我們會分析 $P$ 當中每個字母出現的頻率
接下來建立一個對照的字串 $S$ ， $S$ 當中每個字都會對應到 $P$ 的某個相同出現頻率的字
我們保證題目當中只會出現字母，並且每個字母的出現頻率都不相同
如果給你 $S$ 以及加密後的密文 $C$，你可以找到 $P$ 嗎?
## 想法 By Koios
因為每個字母出現的頻率都是獨特的，所以我們可以先分別統計 $P$ 和 $S$ 的每個字母出現次數
經過排序過後就可以很快對應出每個字母應該要對應到誰
最後建立一個對照表，輸出對著這張表就可以了
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
const int Max = 1e9+10;
int n;
char tbl[128];
bool out=false;
string s;
// 利用 statistics 來進行次數統計
// 根據 cnt 來排序，也記錄下了統計的字母是誰
struct statistics{
char alpha;
// 用一個極大值，使得這些不存在的字元排序後都會在最後方
int cnt=Max;
};
bool cmp(statistics p, statistics q){
if(p.cnt != q.cnt) return p.cnt < q.cnt;
return false;
}
int main(){
cin>>n;
while(n--){
if(out) cout<<"\n";
else out=true;
// 方便起見用 128
statistics text[128], cipher[128];
// 只需要對 A~z 做初始化
for(int i=65 ; i<123 ; i++){
text[i].alpha = cipher[i].alpha = char(i);
text[i].cnt = cipher[i].cnt = 0;
}
cin>>s;
for(int i=0 ; i<s.size() ; i++){
text[s[i]].cnt++;
}
cin>>s;
for(int i=0 ; i<s.size() ; i++){
cipher[s[i]].cnt++;
}
sort(text, text+128, cmp);
sort(cipher, cipher+128, cmp);
for(int i=0 ; cipher[i].cnt!=Max ; i++){
// 建立對照表
tbl[cipher[i].alpha] = text[i].alpha;
}
for(int i=0 ; i<s.size() ; i++){
cout<<tbl[s[i]];
}
cout<<"\n";
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(len(P) + len(C))$
每筆測資統計時間複雜度為 $O(len(P) + len(C))$
每筆測資排序時間複雜度為 $O(2mlogm)$ ，其中 $m = 128$
每筆測資輸出時間複雜度為 $O(len(C))$
總時間複雜度約為 $n(2(len(P) + len(C)) + 2mlogm + len(C))$
# UVa 10041
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10041
有一個人要搬家到某條路上，在這條路上有許多他的親戚，他希望新家能距離所有親戚最近
給每個親戚家所在的座標，問這新房子到其他親戚家距離總和是多少
## 想法 By Koios
首先我們要找到新家的位置，既然要距離所有親戚最近，那就是最中間的位置了(中位數)
要計算中位數，就必須先找到中間項，那麼就先將序列排序吧!如此一來就可以很快找到中間項
找到了新家的座標之後，接下來就計算到每個親戚家的距離總和即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, mid, ans, arr[505];
int main(){
cin>>n;
while(n--){
ans=0;
cin>>m;
for(int i=0 ; i<m ; i++){
cin>>arr[i];
}
sort(arr, arr+m);
// 先找中間項
if(m%2 == 0) mid = (arr[m/2] + arr[m/2-1])/2;
else mid = arr[m/2];
// 計算距離總和
for(int i=0 ; i<m ; i++){
ans += abs(mid - arr[i]);
}
cout<<ans<<"\n";
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(m)$
每筆測資排序時間複雜度為 $O(mlogm)$
每筆測資計算距離總和時間複雜度為 $O(m)$
每筆測資總時間複雜度約為 $O(2m + mlogm)$
# UVa 11362
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11362
我們有很多手機號碼，但是如果有任何一支手機號碼 $p$ 是另一支手機號碼 $q$ 的前綴
那麼在撥號給 $q$ 的時候會先撥到 $p$ ，導致 $q$ 實質上是一隻無用的號碼
現在給你 $n$ 個手機號碼，請問是否每支號碼都是可行的
## 想法 By Koios
要檢查一堆字串是否有前綴相同，最簡單的想法就是先依照字典續排序好
那麼前綴相同的字串就會被排在一起，我們每次都只需要檢查排再一起的連續字串是否相同即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int t, n;
string arr[10010];
bool same_prefix(string p, string q){
for(int i=0, j=0 ; i<p.size() && j<q.size() ; i++, j++){
if(p[i]!=q[j]) return false;
}
return true;
}
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n);
bool ans=true;
for(int i=0, j ; i<n-1 && ans ; i++){
if(same_prefix(arr[i], arr[i+1])){
ans = false;
break;
}
}
if(ans) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n)$
每筆測資排序時間複雜度為 $O(nlogn)$
每筆測資檢查前綴的時間複雜度約為 $O(np)$， $p$ 指的是最長的字串長度
總時間複雜度約為 $O(t(n nlogn + np))$
# UVa 10474
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10474
給了 $n$ 個數字，接下來會有 $q$ 筆詢問
我們想知道這個序列在由小到大排序過後，詢問的數字位在哪個位置，從 1 開始算
## 想法 By Koios
我們可以先將序列排序過後對於每一筆詢問進行二分搜，就可以找到答案了
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, q, Case=1, arr[10010];
int main(){
while(cin>>n>>q && (n!=0 && q!=0)){
cout<<"CASE# "<<Case++<<":\n";
for(int i=0, p ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n);
for(int i=0, p, res ; i<q ; i++){
cin>>p;
res = lower_bound(arr, arr+n, p) - arr;
if(arr[res] == p){
cout<<p<<" found at "<<res+1<<"\n";
}
else{
cout<<p<<" not found\n";
}
}
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n)$
每筆測資排序時間複雜度為 $O(nlogn)$
每筆詢問查詢時間複雜度為 $O(logn)$
每筆測資總時間複雜度為 $O(n + (n+q)logn)$
## 想法 2 By Koios
因為這一題的數字範圍不大，所以我們也可以考慮 counting sort 的解法
去統計每個數字出現的次數，而這些數字做為 index 保證是嚴格遞增，排序也就跟著完成了
接下來的問題就剩下要怎麼回答詢問
我們可以用一個陣列去記錄每個數字出現的次數總和，把當前的總和加 1 就會是當前數字的答案
例如我們有一個已經排序好的序列 $\{1, 2, 2, 3, 4\}$
那麼詢問 $2$ 的答案應該要是 $2$
假如我們已經統計到在 $2$ 以前總共有 $1$ 個數字了，那麼 $1+1 = 2$ 就是 $2$ 的答案
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, q, Case = 1, arr[10010], cnt[10010];
int main(){
while(cin>>n>>q && (n!=0 && q!=0)){
cout<<"CASE# "<<Case++<<":\n";
for(int i=0 ; i<10000 ; i++){
arr[i] = cnt[i] = 0;
}
for(int i=0, p ; i<n ; i++){
cin>>p;
arr[p]++;
}
for(int i=0, Max=0 ; i<10000 ; i++){
if(arr[i] != 0){
cnt[i] = Max+1;
Max+=arr[i];
}
}
for(int i=0, p ; i<q ; i++){
cin>>p;
if(arr[p] != 0){
cout<<p<<" found at "<<cnt[p]<<"\n";
}
else{
cout<<p<<" not found\n";
}
}
}
return 0;
}
```
### 時間複雜度分析
假設 $N = 10000$
每筆測資初始化時間複雜度為 $O(N)$
每筆測資輸入時間複雜度為 $O(n)$
每筆測資統計以及找每個元素的答案的時間複雜度為 $O(N)$
每筆測資詢問時間複雜度為 $O(1)$
每筆測資總時間複雜度為 $O(2N + n + q)$
# UVa 10057
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10057
給一個長度為 $n$ 的序列，求序列的 **最小中位數**、**中位數個數**、**所有符合中位數的正整數**
## 想法 By Koios
1. 最小中位數
序列經過排序後最中間的值就是答案
當序列長度是偶數時，中間兩個數字間的最小值就是答案
2. 中位數個數
如果序列長度是偶數，並且中間兩個元素 $a, b$ 是不同的，因為 $a, b$ 都可以是中位數，所以序列中 $a, b$ 的數量總和就是答案
如果沒有不同的兩個元素或是序列長度是奇數，那麼只需要找 $a$ 的數量總和即可
3. 所有符合中位數的正整數(不重複)
如果序列長度是奇數，因為只有最中間的值可以是中位數，所以答案必定是 $1$
在偶數的狀況下，我們只需要計算中間兩個元素之間包含自己本身總共有多少元素即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, B, C, Min, Max, arr[1000010];
int main(){
while(cin>>n){
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n);
// 先找到最小/最大中位數，順便求出第三個答案
if(n%2 == 0){
Min = arr[n/2-1];
Max = arr[n/2];
C = Max - Min + 1;
}
else{
Min = arr[n/2];
Max = arr[n/2];
C = 1;
}
// 中間有不同的兩個元素
// 計算個數可以直接用二分搜找到數量，也可以用暴力找
if(n%2 == 0 && arr[n/2-1] != arr[n/2])
B = upper_bound(arr, arr+n, Min) - lower_bound(arr, arr+n, Min) + upper_bound(arr, arr+n, Max) - lower_bound(arr, arr+n, Max);
else
B = upper_bound(arr, arr+n, Min) - lower_bound(arr, arr+n, Min);
cout<<Min<<" "<<B<<" "<<C<<"\n";
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n)$
每筆測資排序時間複雜度為 $O(nlogn)$
每筆測資找到 $A$ 以及 $C$ 的時間複雜度都是 $O(1)$
每筆測資找到 $B$ 的時間複雜度最差為 $O(4logn)$
每筆測資總時間複雜度約為 $O(n + 5logn)$
# UVa 755
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?755
有 $n$ 個電話號碼，我們規定一個電話號碼的標準格式是 `3個數字` `-` `4個數字`
例如 `1234-567` 就是一個合法的電話號碼
另外，我們的撥號鍵都會有相對應的英文字母，有時候我們也會用這些英文字母來記憶電話號碼
至於 `-` 開心放多少個就放多少個，但是合法的電話號碼表示中只會在第 3 和第 4 個數字之間有 `-`
現在給你很多雜亂的電話號碼，請你幫忙全部轉換成合法的電話號碼格式，並且找出重複出現的電話號碼分別都是現了幾次
## 想法 By Koios
轉換成合法字串並不困難，我們可以先忽視其中的所有 `-` ，當數字到了 3 個之後再自行加入
並且把所有的英文字母轉換成相對應的數字即可
轉換成合法字串後，要找到重複的字串可以用排序來解決
排序後的序列，會使得相同的字串會被排在一起，那麼我們就只需要再掃過檢查重複即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int t, n;
bool out=false;
// 字串輸入到 s 經過處理放入 arr
string s, arr[100010];
// 從 A~Z 分別對應的數字建立起來
string tbl = "22233344455566677778889999";
int main(){
cin>>t;
while(t--){
if(out) cout<<"\n";
else out=true;
cin>>n;
for(int i=0 ; i<n ; i++){
cin>>s;
// 記得要先初始化
arr[i] = "";
for(int j=0, k=0 ; j<s.size() ; j++){
// 我們只在乎不是 - 的字元
if(s[j] != '-'){
if(s[j]>='0' && s[j]<='9') arr[i] += s[j];
else if(s[j]>='A' && s[j]<='Z') arr[i] += tbl[s[j]-'A'];
// 自己加上 -
k++;
if(k == 3) arr[i] += '-';
}
}
}
sort(arr, arr+n);
bool find_ans=false;
// i 是當前關注的對象
// j 是要和 i 比較的對象
for(int i=0, j ; i<n ; i=j){
for(j=i+1 ; j<n ; j++){
// 找到第一次不相同的位置
if(arr[i] != arr[j]) break;
}
if(j != i+1){
cout<<arr[i]<<" "<<j-i<<"\n";
find_ans=true;
}
}
if(!find_ans)
cout<<"No duplicates.\n";
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n)$
每筆測資預處理 $arr$ 時間複雜度為 $O(\sum_{i=0}^{n-1}{len(s)})$
每筆測資排序時間複雜度為 $O(nlogn)$
每筆測資找重複元素的時間複雜度為 $O(n)$
總時間複雜度為 $t(2n + nlogn + \sum_{i=0}^{n-1}{len(s)})$
###### tags: `SCIST 演算法 題解`
Sign in with Wallet
Connect another wallet