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