d385 - 10905 - Children's Game

🔗 前往 ZeroJudge 原題

題目描述

題目要求給定 N 個正整數，將這些數字以某種順序連接起來，形成一個最大的整數。

解題思路

這題的核心思想是自定義排序規則。直接對數字進行排序無法得到正確結果，例如，9 和 90 比較時，90 應該排在 9 的前面，因為 "990" > "909"。因此，需要定義一個比較函數，比較兩個數字 x 和 y 連接起來的字符串 (x+y) 和 y 連接起來的字符串 (y+x) 的大小，如果 x+y > y+x，則 x 應該排在 y 的前面。使用 std::sort 配合自定義比較函數 cmp 即可實現。

複雜度分析

• 時間複雜度: O(n log n)，主要來自於 std::sort 的排序操作，其中 n 是輸入數字的個數。
• 空間複雜度: O(n)，主要來自於存儲輸入數字的字符串數組 a。

程式碼

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