1038 Recover the Smallest Number

本文主要是介绍1038 Recover the Smallest Number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

idea

给出若干个可能含有前导0的数字串，将其进行拼接使其组成的数最小。
拼接串，想到借助string。
找最小，样例中的32,321, 3214尤为具备代表性，让字典序小的数尽可能靠前，联想到string的比较规则也是字典序
==>判断string字符串s1和s2的前后，需要比较的是它们拼接后形成的数值字典序最小
==>转化为比较s1+s2和s2+s1的字典序，则直接进行比较即可（stl库太香了！！！）

注意1：格式问题。拼接所得的答案串记得去掉前导0，不要忽略样例明示
注意2：边界值处理。给出的数字串非负，则存在全为0的可能。可以直接判断处理后的答案串是否除去前导0为长度为0，若是则直接输出0即可

solution1(测试点3，4不通过)

cmp函数有点问题

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int maxn = 1e4 + 10;
string s[maxn];bool cmp(string s1, string s2){for(int i = 0, j = 0; i < s1.size() && j < s2.size(); i++, j++){if(s1[i] != s2[j]) return s1[i] < s2[j];if(i == s1.size() - 1 && j < s2.size() - 1) i = 0;else if(i < s1.size() - 1 && j == s2.size() - 1) j = 0;} 
}int main(){int n;cin >> n;for(int i = 0; i < n; i++){cin >> s[i];}sort(s, s + n, cmp);for(int i = 1; i < n; i++){s[0] += s[i];}while(s[0].size() && s[0][0] == '0'){//删除前导0 s[0].erase(s[0].begin());}if(s[0].size()) cout << s[0];else cout << 0; return 0;
}

solution

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int maxn = 1e4 + 10;
string s[maxn];bool cmp(string s1, string s2){return s1 + s2 < s2 + s1;
}int main(){int n;cin >> n;for(int i = 0; i < n; i++){cin >> s[i];}sort(s, s + n, cmp);for(int i = 1; i < n; i++){s[0] += s[i];}while(s[0].size() && s[0][0] == '0'){//删除前导0 s[0].erase(s[0].begin());}if(s[0].size()) cout << s[0];else cout << 0; return 0;
}