Koios1143的筆記

Kattis - Sort of Sorting

發表於 分類於

Kattis - Sort of Sorting

題目

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

今天有很多字串要做排序，排序的方式是這樣的

要比較兩個字串的大小，我們只需要看這兩個字串的前兩個字元即可

而這兩組的兩個字元所組成的兩組字串比較方式是字典序

如果說這兩組字串的字典序是相同的，那麼就依照原本的順序排即可

舉例來說，要排序兩個字串 Poincare 以及 Pochhammmer

因為前兩個字的字典序相同，所以依照原本的順序即可 Poincare Pochhammmer

再舉一個例子，要排序兩個字串 Beethoven 以及 Bach

的一個字元的字典序相同，而第二個字的字典序 a 比 e 小，所以放在前面 Bach Beethoven

想法

其實這個排序方式就是所謂的 stable sort， 在 C++ 當中已經有這個函數可以使用

不同的是排序的方式，所以我們要另外寫 compare 函數

比較的方式在前面也有提到就不贅述，詳細可以直接看 code 當中的 cmp()

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//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)$