0%

PTA1038 数字段排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;
//核心,判断哪个数字段排前面的算法
//局部规划+贪婪?,本质上就是先乱序建立好一个数字段,
//交换两个数字段,如果交换后有提升,则采纳;如果无提升,就不采纳
bool cmp(const string& lhs, const string& rhs) {
string temp1 = lhs + rhs;
string temp2 = rhs + lhs;
if (temp1 < temp2) return 1;
else if (temp1 == temp2 && temp1.size() < temp2.size()) return 1;
else return 0;
}
int main() {
int n;
cin >> n;
vector<string> nums;
for (int i=0; i < n; i++) {
string temp;
cin >> temp;
nums.push_back(temp);
}
sort(nums.begin(), nums.end(),cmp);
string result;
for (int i = 0; i < nums.size(); i++) {
result += nums[i];
}
//输入参数全0的情况
int off = result.find_first_not_of('0');
if (off == -1) cout << 0;
else cout << result.substr(off);
}