从文件number.in中读取若干个正整数,求出它们最大的组合数,输出到标准输出中。
输入示例:
123 456 78 782 789
输出示例:
78978782456123
解题思路
将正整数当作字符串读入,然后对这些字符串进行排序,依次对字符串的高位数字进行比较,将高位数字较大的字符串排在前面。注意对长度不等的字符串的处理,比如78和782,应该组合为78782而不是78278。
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
// 对比数字中的每一位(例78 782)
// 1. 对比7和7
// 2. 对比8和8
// 3. 对比7(取余)和2
// 改写cmp
bool cmp(string l, string r) {
int lsize = l.size();
int rsize = r.size();
int maxv = max(l.size(), r.size());
// 循环对比每一位数字(应对长短不一的情况)
for (int i = 0; i < maxv; i++) {
if (l[i % lsize] == r[i % rsize])
continue;
return l[i % lsize] > r[i % rsize];
}
return true;
};
int main() {
vector<string> v;
string s;
while (cin >> s)
v.push_back(s);
// 不可以直接sort,当长短不一的时候可能会出错
sort(v.begin(), v.end(), cmp);
for (auto s : v) cout << s;
return 0;
}