# 演算法課程題解 - 排序
# Kattis - Odd Man Out
## 題目
https://open.kattis.com/problems/oddmanout
有 $N$ 筆測試資料，每筆測試資料包含一個數字 $G$ 以及 $G$ 個數字 $C$
$1 \leq N \leq 50 \quad 0 < C < 2^{31} \quad 3 \leq G \leq 1000$
對於每一筆測試資料，保證只有一個數字只出現過奇數次，求該數字為何
## 想法 By Koios
對於無序的資料，我們可以觀察看看排序之後有沒有特殊的性質可以使用
在這邊我們發現到，當我們將這群數字由小到大排序之後，一樣的數字都會聚集在同一個區域
如此一來，我們就可以直接搜尋過這些相同數字的區域，如果數字個數為奇數，那麼就找到了答案
更進一步的說，我們的步驟會是
1. 輸入資料
2. 將資料由小到大排序
3. 從第 $1$ 個元素開始，每次檢查上一個元素跟自己是否相同
- 相同
將計數器 $+1$
- 不相同
檢查計數器是奇數或是偶數
- 奇數
找到答案輸出
- 偶數
將計數器重整
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n, m, out;
cin>>n;
for(int Case=1 ; Case<=n ; Case++){
cin>>m;
int arr[1005];
for(int i=0 ; i<m ; i++){
cin>>arr[i];
}
sort(arr, arr+m);
// for 迴圈去檢查跟上一個元素是否相同
// cnt 要先算上第 0 個元素
for(int i=1, cnt=1 ; i<=m ; i++){
if(arr[i] == arr[i-1]) cnt++;
else{
if(cnt%2 != 0){
out = arr[i-1];
break;
}
else{
// cnt 要先算上第 i 個元素
cnt=1;
}
}
}
cout<<"Case #"<<Case<<": "<<out<<"\n";
}
return 0;
}
```
### 複雜度分析
輸入的時間複雜度為 $O(n)$
排序的時間複雜度為 $O(nlogn)$
搜尋答案的時間複雜度為 $O(n)$
總時間複雜度 $O(n + nlogn)$
:::success
也許你會很直觀的想要先計算看看每個數字出現的次數，然後再檢查次數是奇數或是偶數
而且這樣做得時間複雜度也很棒，只有 $O(2n)$ 而已
但是要注意到題目的數字範圍最大會到 $2^{31}$ ，所以空間根本不夠使用!
:::
# Zerojudge - b966 線段覆蓋長度
## 題目
https://zerojudge.tw/ShowProblem?problemid=b966
在一維座標上有 $N$ 條線段，給定每個線段的左端座標 $L$ 以及右端座標 $R$，求所有線段覆蓋的總長度
$N < 10000 \quad 0 \leq L, R < 10000000$
## 想法 By Koios
對於一群無序的資料，可以觀察看看在排序之後有沒有特殊的性質可以使用
在這裡我們發現到，如果我們將所有線段先依照左端點座標由小到大排序，再依照又端點座標由小到大排序，會有很好的性質
因為可以保證對於 第 $i$ 條線段與第 $i+1$ 條線段只會有以下 3 種關係
1. 第 $i$ 條線段完全覆蓋第 $i+1$ 條線段
2. 第 $i$ 條線段的右側與第 $i+1$ 條線段的左側有部分重疊
3. 第 $i$ 條線段與第 $i+1$ 條線段完全不相交
接下來我們可以嘗試把每一條覆蓋的線段合併，最後計算合併後的總長度即可
針對 3 種情況分別這樣處理:
- 對於第一種情況
將第 $i+1$ 條線段變成第 $i$ 條線段
- 對於第二種情況
將第 $i+1$ 條線段的左端點更新成第 $i$ 條線段的左端點
- 對於第三種情況
計算第 $i$ 條線段的長度，加入到答案之中
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
struct line{
int L;
int R;
};
bool cmp(line p, line q){
if(p.L < q.L) return true;
else if(p.L == q.L) return p.R <= q.R;
else return false;
}
int main(){
line arr[10010];
int n;
cin>>n;
for(int i=0, L, R ; i<n ; i++){
cin>>L>>R;
arr[i].L = L;
arr[i].R = R;
}
sort(arr, arr+n, cmp);
int ans=0;
for(int i=0 ; i<n-1 ; i++){
if(arr[i].R > arr[i+1].R){
// 情況一: 完全覆蓋
arr[i+1].L = arr[i].L;
arr[i+1].R = arr[i].R;
}
else if(arr[i].R <= arr[i+1].R && arr[i].R >= arr[i+1].L){
// 情況二: 部分覆蓋
arr[i+1].L = arr[i].L;
}
else{
// 情況三: 不相交
ans += (arr[i].R - arr[i].L);
}
}
// 記得最後要算上最後一條線段
ans += (arr[n-1].R - arr[n-1].L);
cout<<ans<<"\n";
return 0;
}
```
### 複雜度分析
輸入的時間複雜度為 $O(n)$
排序的時間複雜度為 $O(nlogn)$
遍歷線段的時間複雜度為 $O(n)$
總時間複雜度為 $O(n + nlogn)$
# Kattis - Conformity (UVa 11286)
## 題目
https://open.kattis.com/problems/conformity
http://domen111.github.io/UVa-Easy-Viewer/?11286
在一間大學當中有 $n$ 個學生，每個學生都可以選擇 5 種課程，並且課程以介於 $100$ ~ $499$ 之間的數字表示
每個學生選擇的課程會形成一個課程組合
現在學校想要統計每種課程組合有多少學生選擇，並且表揚那些選擇最受歡迎課程組合的學生
輸出總共要表揚多少學生
$1 \leq n \leq 10000$
## 想法 By Koios
首先我們要先界定一下相同的課程組合，只要選擇的課程內容相同就是同一個課程組合
但是選擇的先後順序不同會讓我們很困擾，所以首先將所有學生選擇的課程按照其編號由小到大排序好
接下來，對我們來說全部學生的課程組合就是一群無序的資料了，針對這群無序的資料可以觀察排序後有沒有甚麼好的性質可以使用
我們會發現到，當我們將這群資料由小到大排序後，相同的課程組合會被放在一起
那麼我們只需要去統計這幾群相同的序列(相同的課程組合)總共有多少組，然後記錄下最多組的人數總和即可
那麼，要怎麼排序這群無序的資料呢?
一種方法是很直觀的依序依照每個元素的大小來排序，自訂一個 compare function
另一種想法是這樣的，首先觀察到每個學生只能選擇 $5$ 種課程，並且課程編號都是 $3$ 位數
那麼，將這些數字組合起來會是一個 $15$ 位數的數字，範圍在 long long 內
這樣就可以將這一群資料變成一個序列了!
詳細來說，我們的步驟是這樣
1. 輸入
2. 將每一位學生選擇的課程由小到大排序
3. 將每個學生的課程組合組成一個 $15$ 位數的數字
4. 將課程組合由小到大排序
5. 從第 $1$ 個課程組合開始遍歷
- 如果課程組合 $i$ 和課程組合 $i-1$ 相同
將計數器 $+1$
- 如果課程組合 $i$ 和課程組合 $i-1$ 不相同
- 如果計數器的數值大於當前紀錄的最大值
更新最大值，並且更新答案
- 如果計數器的數值等同當前紀錄的最大值
將答案加上計數器的數值
無論如何都要將計數器重整
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, arr[10000][5];
long long num[10000];
int main(){
cin>>n;
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<5 ; j++){
cin>>arr[i][j];
}
// 先將每個學生的課程排序
sort(arr[i], arr[i]+5);
// 再來組合成 15 位數
for(int j=0 ; j<5 ; j++){
num[i] *= 100;
num[i] += arr[i][j];
}
}
// 接著排序所有課程組合
sort(num, num+n);
// 先記錄下第一組課程組合
int Max = 1, ans=1;
for(int i=1, cnt=1 ; i<n ; i++){
if(num[i] == num[i-1]) cnt++;
else{
if(cnt > Max){
Max = cnt;
ans = cnt; // 當前是最新的最大值，答案正是計數器的值
}
else if(cnt == Max){
ans += cnt;
}
// 要記錄第 i 個數
cnt=1;
}
}
cout<<ans<<"\n";
return 0;
}
```
### 複雜度分析
輸入時間複雜度為 $O(n)$
排序所有學生課程的時間複雜度為 $O(5nlog5) \approx O(n)$
所有學生組合成 15 位數的時間複雜度為 $O(5n) \approx O(n)$
排序所有課程組合的時間複雜度為 $O(nlogn)$
遍歷所有課程組合的時間複雜度為 $O(nlogn)$
總時間複雜度為 $O(3n + 2nlogn) \approx O(n + nlogn)$
# Kattis - Planting Trees
## 題目
https://open.kattis.com/problems/plantingtrees
有一個園丁要種樹，每棵樹要花上一天的時間播種，並且因為園丁很懶惰，所以一天只會播種一棵樹的種子
聰明的園丁已經知道每棵樹會花幾天成長完成，並且園丁可以自己選擇每顆樹種下的順序
園丁想知道最後一顆樹成長完成的隔天是第幾天(從 1 開始計算)
輸入包含一個正整數 $N$，接下來有 $N$ 個正整數 $t_i$ 表示每棵樹的成長時間
$1 \leq N \leq 100000 \quad 1 \leq t_i \leq 1000000$
## 想法 By Koios
因為題目當中只有限制每天只能種一棵樹，但是並沒有限制要一顆樹完全成長後才能繼續種植，所以最佳解很顯然的是要從 $t_i$ 最大的樹開始種植
也就是說我們先依照種植時間由大到小排序，接下來模擬整個種樹的情況
記錄下當前剩餘成長日的最大值 $M$
若 $t_i > M$，就將 $M$ 更新成 $t_i$
而每一輪的模擬都需要將 $M$ 遞減，並且將答案遞增
詳細來說，我們的步驟是這樣
1. 輸入資料
2. 將資料由大到小排序
這部分也可以由小到大排序，後面遍歷從後面往前面走即可
3. 紀錄當前最大剩餘成長日 $M$ 為第 $1$ 個元素
4. 因為每棵樹第一天都要先種植，答案先預設為 $1$
5. 模擬接下來的 $n-1$ 天
- 每天將 $M$ 遞減
- 每天將答案遞增
- 如果 $t_i > M$
- 更新 $M = t_i$
6. 最後答案加上剩餘的 $M$ 再加上 $1$ 表示隔天
### 程式碼
```cpp=
// By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n, arr[100010];
cin>>n;
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n);
// 由小到大排序，所以由後往前取元素
int days=arr[n-1], ans=1;
for(int i=n-2 ; i>=0 ; i--, ans++){
days--;
if(arr[i] > days)
days = arr[i];
}
ans += (days+1);
cout<<ans<<"\n";
return 0;
}
```
### 複雜度分析
輸入時間複雜度為 $O(n)$
排序時間複雜度為 $O(nlogn)$
遍歷所有成長時間的時間複雜度為 $O(n)$
總時間複雜度為 $O(n + nlogn)$
# Kattis - Sticky Situation
## 題目
https://open.kattis.com/problems/stickysituation
給定 $N$ 個正整數數字 $n$，求是否有任三個數字能組成三角形 ($a+b>c$)
$3 \leq N \leq 20000 \quad 1 \leq n \leq 2^{60}$
### 想法 By Koios
對於一群無序的序列，可以觀察看看排序後是否有好的性質
在這一題當中，我們要試圖找到 $a, b, c$，其中 $a \leq b \leq c$ 且 $a + b > c$
前提條件當中的 $a \leq b \leq c$ 可以直接透過由小到大排序解決
接下來也許你會想到，我們可以由小到大枚舉三角形的三邊長，然後判斷是否符合
但是真的有必要枚舉所有情況嗎?
假如我們先選擇了三個不連續的數字 $i, i+a, i+b \ (a < b)$
如果說這三個不連續的數字能形成三角形，因為是遞增序列，可以保證 $i+(a-1), i+a, i+b$ 也一定會成立
同理， $i+(b-2), i+(b-1), i+b$ 也會成立
用更簡單的方式來說，我們只需要去枚舉連續的三個元素是否符合即可
也就是只需要檢查 $i, i+1, i+2$ 即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
long long arr[20010];
cin>>n;
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n);
bool possible=false;
for(int i=0 ; i<n-2 ; i++){
if(arr[i] + arr[i+1] > arr[i+2]){
possible=true;
break;
}
}
if(possible) cout<<"possible\n";
else cout<<"impossible\n";
return 0;
}
```
### 複雜度分析
輸入時間複雜度為 $O(n)$
排序時間複雜度為 $O(nlogn)$
遍歷時間複雜度為 $O(n)$
總時間複雜度為 $O(n + nlogn)$
# Kattis - Bus Numbers
## 題目
https://open.kattis.com/problems/busnumbers
給一個序列，如果有連續遞增 $1$ 的子序列 $a_i$ ~ $a_j$ 長度超過 $2$ ，那麼就可以化簡成 `a_i-a_j`
否則正常輸出每個數字
例如有一個序列 $(141, 142, 143, 145)$ 經過化簡後會變成 `141-143 145`
### 想法 By Koios
可以化簡的是連續遞增的序列，那麼很容易可以想到先將序列排序
排序之後檢查每個連續的子序列長度，若超過 $2$ 就輸出化簡的結果，否則正常輸出即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n, arr[1010];
bool out=false;
cin>>n;
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n);
for(int i=1, cnt=1 ; i<=n ; i++){
// 當 i==n 時是看到最後一個元素的時候
// 此時直接進入輸出階段
if(arr[i]-1 == arr[i-1] && i!=n){
cnt++;
}
else{
// 輸出之間要有空隔間格
if(out) cout<<" ";
else out=true;
if(cnt>2){
// 輸出化簡的結果
cout<<arr[i-cnt]<<"-"<<arr[i-1];
}
else if(cnt==2){
// 長度剛好為 2，將兩個元素都正常輸出
cout<<arr[i-2]<<" "<<arr[i-1];
}
else{
cout<<arr[i-1];
}
cnt=1;
}
}
cout<<'\n';
return 0;
}
```
### 複雜度分析
輸入時間複雜度為 $O(n)$
排序時間複雜度為 $O(nlogn)$
遍歷時間複雜度為 $O(n)$
總時間複雜度為 $O(n + nlogn)$
# UVa 10327
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10327
題目包含多筆測試資料，每筆測試資料第一行有一個正整數 $n$，接下來有 $n$ 個數字
求將這個序列由小到大排序需要最少只需要交換多少次
$n \leq 1000$
## 想法 By Koios
因為這一題的 $n$ 很小，所以我們可以直接實作 bubble sort，然後計算我們總共交換了幾次
如果說 $n$ 很大，那就需要用 merge sort 來實作，不過這裡就不實作了
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, ans, arr[1005];
int bubble_sort(){
ans=0;
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<n-1-i ; j++){
if(arr[j] > arr[j+1]){
swap(arr[j], arr[j+1]);
ans++;
}
}
}
return ans;
}
int main(){
while(cin>>n){
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
bubble_sort();
cout<<"Minimum exchange operations : "<<ans<<"\n";
}
return 0;
}
```
### 複雜度分析
每筆測資輸入時間複雜度為 $O(n)$
每筆測資排序時間複雜度為 $O(n^2)$
每筆測資總時間複雜度為 $O(n + n^2)$
# UVa 555
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?555
現在我們要來玩一場橋牌，一場橋牌當中會有一個玩家負責發牌，並且我們會以方位(`N`, `E`, `S`, `W`)來稱呼玩家
發牌會從發牌者的左手邊開始，逆時針方向發牌，直到第 52 張牌被發到發牌玩家
在發牌結束後，我們需要將所有玩家的手牌依照其大小由小到大排序
每張牌都會有一個花色以及一個數字，其大小順序如下
- 花色
`C` < `D` < `S` < `H`
- 數字
`2` < `3` < `4` < `5` < `6` < `7` < `8` < `9` < `T` < `J` < `Q` < `K` < `A`
最後依照 `S` `W` `N` `E` 的順序輸出排序後的手牌
## 想法 By Koios
就直接照著題目的意思去模擬
排序的部分自訂一個 compare function
如果要避免寫太多 if-else 來判斷彼此之間的大小，可以預先建立一個表儲存每個元素對應到的數字
只要保證這些數字之間的大小關係跟題目中要求的元素之間大小關係相同即可
### 程式碼
```cpp=
// By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int player, pos[128], order[128];
char n, color, number;
string card, cards[4][13];
// 為了方便建表，這裡先建立兩個已經排好的字串
string pos_str="SWNE", card_str="CDSH23456789TJQKA";
bool cmp(string p, string q){
// 直接比較元素之間的大小關係即可
if(order[p[0]] != order[q[0]]) return order[p[0]] < order[q[0]];
else if(order[p[1]] != order[q[1]]) return order[p[1]] < order[q[1]];
else return false;
}
int main(){
// 預先建方位對應數字的表
for(int i=0 ; i<4 ; i++){
pos[pos_str[i]] = i;
}
// 預先建立卡牌顏色以及數字對應的數字表
for(int i=0 ; i<card_str.size() ; i++){
order[card_str[i]] = i;
}
while(cin>>n && n!='#'){
// 這裡可以直接用數字表示方位了!
player = pos[n];
for(int i=0, j=0 ; i<52 ; i++){
// 每次都是發給下一位玩家
player = (player+1)%4;
cin>>color>>number;
// 把顏色以及數字串起來
// 注意不能直接用字原相加
card = "";
card.push_back(color);
card.push_back(number);
cards[player][j] = card;
// 每經過 4 次，就表示已經發完一輪牌了
if((i+1)%4 == 0) j++;
}
for(int i=0 ; i<4 ; i++){
sort(&cards[i][0], &cards[i][13], cmp);
}
for(int i=0 ; i<4 ; i++){
cout<<pos_str[i]<<": ";
for(int j=0 ; j<13 ; j++){
if(j!=0) cout<<" ";
cout<<cards[i][j];
}
cout<<"\n";
}
}
return 0;
}
```
### 時間複雜度分析
預處理時間複雜度為 $O(1)$ ($O(21)$可以直接視為常數)
每筆測資輸入時間複雜度為 $O(n)$ ($n = 52$)
每筆測資排序時間複雜度為 $O(nlogn)$
每筆測資輸出時間複雜度為 $O(n)$
每筆測資總時間複雜度為 $O(n + nlogn)$
# UVa 11321
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11321
給定一個長度為 $n$ 的序列以及一個正整數 $m$
根據以下的規則排序
- 若 $p \% m < q \% m$
$p$ 排在 $q$ 前面
- 若 $p \% m > q \% m$
$q$ 排在 $p$ 前面
- 若 $p \% m = q \% m$
- 若 $p, q$ 皆為偶數
小的排前面
- 若 $p, q$ 皆為奇數
大的排前面
- 否則
奇數的排前面
## 想法 By Koios
只需要根據題目的意思自訂 compare function 即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n, m, arr[10010];
bool cmp(int a, int b){
if(a%m != b%m) return a%m < b%m;
else{
if(a%2==0 && b%2==0) return a < b;
else if(abs(a%2)==1 && abs(b%2)==1) return a > b;
else return abs(a%2)==1;
}
}
int main(){
while(cin>>n>>m && (n!=0 && m!=0)){
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n ,cmp);
cout<<n<<" "<<m<<"\n";
for(int i=0 ; i<n ; i++){
cout<<arr[i]<<"\n";
}
}
cout<<"0 0\n";
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n)$
每筆測資排序時間複雜度為 $O(nlogn)$
每筆測資輸出時間複雜度為 $O(n)$
每筆測資總時間複雜度為 $O(n + nlogn)$
# Kattis - Sort of Sorting
## 題目
https://open.kattis.com/problems/sortofsorting
今天有很多字串要做排序，排序的方式是這樣的
要比較兩個字串的大小，我們只需要看這兩個字串的前兩個字元即可
而這兩組的兩個字元所組成的兩組字串比較方式是字典序
如果說這兩組字串的字典序是相同的，那麼就依照原本的順序排即可
:::info
補充: 字典序
字典序指的是依照 `A-Z` 以及 `a-z` 的方式排列，更廣義的來說，你可以參考 ascii table 每個字所對應的數值，我們就是依照這個大小來比較的
在 C++ 當中，我們可以用 `int(c)` 來找到字元 `c` 所對應到的數值
:::
舉例來說，要排序兩個字串 `Poincare` 以及 `Pochhammmer`
因為前兩個字的字典序相同，所以依照原本的順序即可 `Poincare Pochhammmer`
再舉一個例子，要排序兩個字串 `Beethoven` 以及 `Bach`
的一個字元的字典序相同，而第二個字的字典序 `a` 比 `e` 小，所以放在前面 `Bach Beethoven`
## 想法 By Koios1143
其實這個排序方式就是所謂的 stable sort， 在 C++ 當中已經有這個函數可以使用
不同的是排序的方式，所以我們要另外寫 compare 函數
比較的方式在前面也有提到就不贅述，詳細可以直接看 code 當中的 `cmp()`
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
string arr[205];
bool cmp(string p, string q){
// 先比較第一個字元
if(int(p[0]) != int(q[0])){
return int(p[0]) < int(q[0]);
}
// 再比較第二個字元
else{
if(int(p[1]) != int(q[1])){
return int(p[1]) < int(q[1]);
}
}
// false 表示字典序 p>=q
return false;
}
int main(){
int n;
bool out=false;
while(cin>>n && n){
// 在輸出之間需要有換行
if(out) cout<<"\n";
else out = true;
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
stable_sort(arr, arr+n, cmp);
for(int i=0 ; i<n ; i++){
cout<<arr[i]<<"\n";
}
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度 $O(n)$
每筆測資排序時間複雜度 $O(nlogn)$
每筆測資輸出時間複雜度 $O(n)$
每筆測茲的總時間複雜度約為 $O(n + nlogn)$
# Kattis - Sideways Sorting
## 題目
https://open.kattis.com/problems/sidewayssorting
一般來說我們排序字串都是由左到右，但是本題要我們由上到下來看
輸入第一行包含兩個正整數 $r, c$，表示 row 與 column
接下來有 $r$ 行，每行 $c$ 個字元
最後輸出垂直方向由上到下的**穩定排序**
並且排序過程當中忽略大小寫
舉例來說
```
oTs
nwi
eox
```
從垂直的方向來看，我們會得到三個字串
```
one
Two
six
```
接下來排序這幾個字串
```
one
six
Two
```
最後排回原本的橫向
```
osT
niw
exo
```
## 想法 By Koios
因為排序的方向是垂直的，我們可以直接以垂直的方式儲存這些字串即可
接下來穩定排序過後在改變輸出的方向即可
至於排序的部分，我們可以先把所有要比較的字串先都轉換成小寫之後再來比較大小
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
string arr[20];
bool cmp(string p, string q){
// 先轉換成小寫
for(int i=0 ; i<p.size() ; i++){
p[i] = tolower(p[i]);
}
for(int i=0 ; i<q.size() ; i++){
q[i] = tolower(q[i]);
}
// 接下來再比較大小
if(p != q) return p<q;
return false;
}
int main(){
int r,c;
char tmp;
bool out=false;
while(cin>>r>>c && (r!=0 && c!=0)){
// 輸出之間需要有換行
if(out) cout<<"\n";
else out=true;
// 初始化所有字串
for(int i=0 ; i<c ; i++){
arr[i] = "";
}
for(int i=0 ; i<r ; i++){
for(int j=0 ; j<c ; j++){
// 把字串串起來
cin>>tmp;
arr[j]+=tmp;
}
}
stable_sort(arr, arr+c, cmp);
for(int i=0 ; i<r ; i++){
for(int j=0 ; j<c ; j++){
// 記得輸出方向是相反
cout<<arr[j][i];
}
cout<<"\n";
}
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(rc)$
每筆測資初始化時間複雜度為 $O(rc)$
每筆測資排序時間複雜度為 $O((len(p) + len(q)) \times nlogn)$
每筆測資輸出時間複雜度為 $O(rc)$
每筆測資總時間複雜度約為 $O(rc + nlogn)$ ($len(p) + len(q)$ 很小，可以忽視)
###### tags: `SCIST 演算法 題解`
Sign in with Wallet
Connect another wallet