d634 - 魔法卡magic

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取 n 個字串，並依照類似檔案系統的排序方式進行排序後輸出。排序規則是按照字串中每個字元的 ASCII 值進行比較，空格 < 數字 < 大寫字母 < 小寫字母。

解題思路

這題的核心在於實作一個自定義的字串比較函數，以符合題目所定義的排序規則。程式首先讀取字串的數量 n，然後讀取 n 個字串。為了確保所有字串長度一致，程式會將長度小於 10 的字串補足空格至長度為 10。接著，使用 std::sort 函數和自定義的比較函數 cmp 對字串陣列進行排序。最後，輸出排序後的字串陣列。比較函數 cmp 逐一比較字串的每個字元，直到遇到不同的字元或到達字串的末尾。

複雜度分析

• 時間複雜度: O(n log n)，其中 n 是字串的數量。這是因為 std::sort 通常使用快速排序或歸併排序等演算法，其時間複雜度為 O(n log n)。比較函數 cmp 的時間複雜度為 O(m)，其中 m 是字串的最大長度，但由於 m 是常數 (10)，因此可以忽略。
• 空間複雜度: O(n)，主要用於儲存字串陣列。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
inline bool cmp(string x,string y){
	for(int i=0;i<=11;++i){
		if(x[i]>y[i])
			return 0;
		else if(x[i]<y[i])
			return 1;
	}
	return 0;
}
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int a;
	cin >> a;
	string b[a];
	getline(cin,b[0]);
	for(int i=0;i<a;++i){
		getline(cin,b[i]);
		for(int j=b[i].length();j<=10;++j){
			b[i]+=' ';
		}
	}
	sort(b,b+a,cmp);
	for(int i=0;i<a;++i)
		cout << b[i] << "\n";
}