20241024每日一题洛谷P1012

普及-洛谷P1012 拼数

设有 n 个正整数，a₁ a₂ a₃ ......a_n 将它们联接成一排，相邻数字首尾相接，组成一个最大的整数

输入：

第一行有一个整数，表示数字个数 n

第二行有 n个整数，表示给出的 n个整数 a_i

输出：

一个正整数，表示最大的整数

可以考虑两种路线：使用sort函数编辑cmp参数进行字符串拼接排序、使用字符串基数排序最高位优先（msd）

首先解释第一种方法：

我们需要知道这一条规则，假设有字符串 a，b，他们首位拼接最简单的办法：

直接使用+运算符

string a = "hello ";
string b = "world!";
string c = a + b;

其中 c 就是以 a 为开头 b 为结尾的拼接后的字符串

再来配置cmp参数：

bool cmp (string a,string b){
	return a + b > b + a;
}

这段函数表示，返回a+b和b+a两者之中的最大值

补充：字符串的比较规则

从左到右逐字符比较，第一个不同的字符决定大小，如果一个字符串是另一个字符串的前缀，则较短的字符串更小

最后使用sort函数完成排序

sort(numbers.begin(), numbers.end(), cmp);

关于cmp函数的优化方案(无O2优化的情况下)

传值时直接传入地址，避免复制的操作：

bool cmp (string &a,string &b){
	return a + b > b + a;
}

完整代码如下：

// 自定义比较函数
bool cmp(const string &a, const string &b) {
    return a + b > b + a;
}
int main() {
    int n;
    cin >> n;
    vector<string> numbers(n);
    for (int i = 0; i < n; i++) cin >> numbers[i];
    sort(numbers.begin(), numbers.end(), cmp);
    for (const auto &num : numbers) cout << num;//遍历vector容器
    return 0;
}

埋坑：字符串基数排序最高位优先（msd）