b051 - 2. 排列最大值

🔗 前往 ZeroJudge 原題

題目描述

題目要求給定 N 個正整數，將它們連接成一個字串，並找出所有可能的連接方式中，數值最大的一個字串。

解題思路

這題的核心思想是自定義一個比較函數，用於比較兩個數字字串的連接結果。具體來說，對於兩個字串 a 和 b，比較 a+b 和 b+a 的大小，如果 a+b 大於 b+a，則認為 a 應該排在 b 的前面。然後，使用排序演算法（這裡使用 std::sort）按照這個自定義的比較函數對輸入的數字字串進行排序。最後，將排序後的字串連接起來，即可得到最大值。這是一種貪心策略，因為每次比較都選擇當前能產生最大連接結果的順序。

複雜度分析

• 時間複雜度: O(n log n)，其中 n 是輸入數字的個數。這是因為排序操作通常具有 O(n log n) 的時間複雜度。字串連接和比較操作在每次比較中執行，但它們的複雜度相對較小，不會影響整體的時間複雜度。
• 空間複雜度: O(n)，主要用於儲存輸入的數字字串。

程式碼

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
bool cmp(string a,string b){
	if(a.length()==b.length())
		return a>b;
	if(a+b>b+a)
		return 1;
	return 0;
}
int main(){
	int a;
	while(cin >> a){
		string b[a];
		for(int i=0;i<a;i++)
			cin >> b[i];
		sort(b,b+a,cmp);
		for(int i=0;i<a;i++)
			cout << b[i];
		cout << "\n";
	}
}