n327 - The Tower of Names
題目描述
題目要求讀取 n 個英文姓名，並按照特定規則進行排序後輸出。排序規則為：首先按照姓名長度升序排序，如果姓名長度相同，則按照字典序（字母順序）升序排序。
解題思路
本題的核心是實現一個自定義的排序函數，用於比較兩個字符串的長度和字典序。首先，比較兩個字符串的長度，如果長度不同，則長度較短的字符串排在前面。如果長度相同，則比較兩個字符串的字典序，按照字典序升序排列。使用 std::sort 函數和自定義的比較函數可以輕鬆地實現這個排序過程。
複雜度分析
- 時間複雜度: O(n log n) (主要來自
std::sort的排序操作，其中 n 是姓名數量) - 空間複雜度: O(n) (用於存儲姓名字符串的
std::vector)
程式碼
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int n;
std::cin >> n;
std::cin.ignore(); // Ignore the newline character after n
std::vector<std::string> names(n);
for (int i = 0; i < n; ++i) {
std::getline(std::cin, names[i]);
}
std::sort(names.begin(), names.end(), [](const std::string& a, const std::string& b) {
if (a.size() == b.size()) {
return a < b; // Alphabetical order for names of the same length
} else {
return a.size() < b.size(); // Length order
}
});
for (const auto& name : names) {
std::cout << name << '\n';
}
return 0;
}