PAT A1038

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given {32, 321, 3214, 0229, 87}, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.

Input Specification:

Each input file contains one test case. Each case gives a positive integer N (<=10000) followed by N number segments. Each segment contains a non-negative integer of no more than 8 digits. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the smallest number in one line. Do not output leading zeros.

Sample Input:
5 32 321 3214 0229 87
Sample Output:
22932132143287

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
#include "stdio.h"
//#include "math.h"
#include "string.h"
#include "algorithm"
#include "iostream"
using namespace std;
const int maxn = 10010;
string str[maxn];
bool cmp(string a, string b){
return a + b < b + a;//如果a+b < b+a 就把a排在前面
}
int main(){
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> str[i];
}
sort(str, str + n, cmp);
string ans;
for (int i = 0; i < n; i++) {
ans += str[i];
}
while (ans.size() != 0 && ans[0] == '0') {
ans.erase(ans.begin());//去除前导0
}
if (ans.size() == 0) {
cout << 0;
}else{
cout << ans;
}
return 0;
}

对于字符串S1 S2,如果S1+S2 <S2+S1(+表示拼接),那么把S1放在S2前面。
其次string处理字符串真的强!
如果串的大小不为0,要去除前面的所有0;
附上需要用上的string函数(需要引用iostream 和 string)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(1) += 直接拼接
(2) == != < <= > >= 比较大小 字典序
(3) length()/size() 返回string的长度
(4) insert()
1. str.insert(pos,string) 在pos位置插入字符串string
2. str.insert(it,it2,it3) 在it的位置插入字符串的首尾it2,it3
(5) erase()
1. str.erase(it) 删除单个元素,it为元素迭代器
2. str.erase(first, last) 删除区间内的所有元素 first和last都为元素迭代器
3. str.erase(pos,length) pos为需要开始删除的起始位置
(6) clear() 清空string中的数据
(7) substr(pos,len) 返回从pos号开始的长度为len的子串
(8) string:npos 常数,本身值为-1 用以作为find函数失败匹配时的返回值。在unsigned_int类型中 -1 也为4294967295
(9) find()
1. str.find(str2) 返回str2在str中的位置,如果没找到,则返回string:npos
2. str.find(pos, str2) 返回从pos找起的str2在str中的位置,如果没找到,则返回string:npos
(10) replace()
1. str.replace(pos, len, str2) 把str2 从pos开始,长度为len换成str2
2. str.replace(it1, it2, str2) 把str的迭代器[it1,it2)范围的子串替换为str2