k645 - 數學得力工具

🔗 前往 ZeroJudge 原題

題目描述

題目要求將輸入的包含數字和加號的字串，重新排列數字的順序，使得數字以非遞減順序排列，並輸出重新排列後的字串。輸入字串只包含數字 1、2 和 3，以及加號。

解題思路

這題的解題思路很簡單。首先，我們需要從輸入字串中提取所有的數字。然後，將這些數字儲存在一個陣列中。接著，對這個陣列進行排序，使其按照非遞減順序排列。最後，將排序後的數字重新組合成一個字串，並在數字之間插入加號。

複雜度分析

• 時間複雜度: O(n log n)，其中 n 是輸入字串中數字的個數。排序操作的時間複雜度為 O(n log n)，其餘操作的時間複雜度為 O(n)。
• 空間複雜度: O(n)，其中 n 是輸入字串中數字的個數。我們需要一個陣列來儲存提取出的數字。

程式碼

#include <bits/stdc++.h>
using namespace std;
int a[1005],n;
char c;
int main(){
	while(cin >> a[n]){
		++n;
		cin >> c;
	}
	sort(a,a+n);
	for(int i=0;i<n;++i){
		if(i)cout << "+";
		cout << a[i]; 
	}
}