[PAT] A1038 Recover the Smallest Number

(贪心、字符串)

题目大意

给一些字符串，求它们拼接起来构成最小数字的方式

思路

贪心算法。用cmp排序，直接判断a+b和b+a的大小即可。 必须保证两个字符串构成的数字是最小的才行，所以cmp函数写成return a + b < b + a;的形式，保证它排列按照能够组成的最小数字的形式排列。 因为字符串可能前面有0，这些要移除掉（用s.erase(s.begin())就可以了）。输出拼接后的字符串即可。 注意：如果移出了0之后发现s.length() == 0了，说明这个数是0，那么要特别地输出这个0，否则会什么都不输出。

AC代码

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<iostream> #include<vector> #include<queue> #include<string.h> #include<algorithm> using namespace std; #define MAX 10002 bool cmp(string a, string b) { return a + b < b + a; } int main() { string input[MAX]; int i = 0; int num; cin >> num; for (i = 0;i < num;i++) cin >> input[i]; sort(input, input + num, cmp); bool flag = 0; string ans; for (i = 0;i < num;i++) ans += input[i]; while (ans.size() != 0 && ans[0] == '0') ans.erase(ans.begin()); if (ans.size() == 0) cout << 0; else cout << ans; return 0; }

AC代码2（复杂）

一开始我没想到直接可以a+b拼接判断，还考虑了多种情况。在处理首位0的时候也比较复杂。 要学会充分利用cmp和string的功能啊。。。。。。

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<iostream> #include<vector> #include<queue> #include<string.h> #include<algorithm> using namespace std; #define MAX 10002 bool cmp(string a, string b) { if (a.size() == b.size())return a < b; int i = 0, j = 0; while (1) { if (a[i] != b[j]) return a[i] < b[j]; i++;j++; if (i >= a.size() && j >= b.size()) return 0; if (i >= a.size()) i = i - a.size(); if (j >= b.size()) j = j - b.size(); } //return a + b < b + a; } int main() { string input[MAX]; int i = 0; int num; cin >> num; for (i = 0;i < num;i++) cin >> input[i]; sort(input, input + num, cmp); bool flag = 0; for (i = 0;i < num;i++) { if (flag == 0) { for (int j = 0;j < input[i].size();j++) { if (flag==0 && input[i][j] != '0'){ flag = 1; cout << (int)(input[i][j] - '0'); } else if (flag == 1) cout << (int)(input[i][j] - '0'); } } else cout << input[i]; } if (flag == 0)cout << 0; return 0; }