PAT刷题记录 1038 Recover the Smallest Number
Recover the Smallest Number
#include <iostream>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
vector<string> num;
bool cmp1(string a, string b)
{
int la = a.length(), lb = b.length();
string temp;
if (la == lb)
return a <= b;
else if (la < lb) //自己重新定义字符串比较的定义
{
if (a.compare(b.substr(0, la)) == 0)
{
temp = b.substr(la) + a;
if (temp <= b)
return false;
else
return true;
}
else
return a <= b;
}
else if (la > lb)
{
if (b.compare(a.substr(0, lb)) == 0)
{
temp = a.substr(lb) + b;
if (temp <= a)
return true;
else
return false;
}
else
return a <= b;
}
}
int main()
{
int n;
cin >> n;
string s;
for (int i = 0; i < n; ++i)
{
cin >> s;
num.push_back(s);
}
sort(num.begin(), num.end(), cmp1);
int len = num.size();
string ans = "";
for (int i = 0; i < len; ++i)
{
ans += num[i];
}
int pos = 0;
bool flag = false;
for (int i = 0; i < ans.length(); ++i)
{
if (ans[i] != '0')
{
pos = i;
flag = true;
break;
}
}
if (flag == false) //要注意全是0的情况!
cout << "0";
else
cout << ans.substr(pos);
return 0;
}
若一长一短且短的那个是长的的前缀,重新定义比较的标准。cmp定义了何时a<b,所以自己根据需要的情况直接返回true或false
substr的用法:
-
s.substr(5)
截取从s[5]到结尾
-
s.substr(0,5)
从s[0]开始截取5位
AC了之后看别人的代码,哭了,我好傻写那么长,直接把比较的标准定义成a+b<b+a就完了…
bool cmp0(string a, string b) {
return a + b < b + a;
}
最后修改于 2020-04-19