题解：P1012 [NOIP 1998 提高组] 拼数

Lemon_zqp · 2025-08-08 20:29:01 · 题解

思路 + 证明

这题明显贪心，先把所有数按照字符串输入进来，很容易想到的一个就是按照 return a + b > b + a 来对字符串进行排序。接下来将用一种简单的方式证明为何这种策略是对的。

首先，我们不妨设正整数 a 的位数为 m，b 的位数为 n。那么不难发现将 a 与 b 拼接在一起的最大值就是先 a 后 b 和先 b 后 a 两种拼接方式拼出的最大值，即 a \times 10^n + b 和 b \times 10^m + a 的最大值。那么将 a 和 b 转为字符串。拼接起来也同样两种形式，先 a 后 b 的 a + b 和先 b 后 a 的 b + a。那么如何比较这两个的大小？显然可以直接比较两个字符串，毕竟越大的数字越靠前，整个数字显然更大。到这里就推出了 a + b > b + a 这一贪心策略。

代码

//I'm milk dragon
#include<bits/stdc++.h>
const int N = 25;
using namespace std;

string s[N];

bool cmp(string a, string b)
{
    return a + b > b + a;  //套用贪心策略，如果a + b更大，就让 a 排在 b 前面
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) 
    {
        cin >> s[i];
    }
    sort(s + 1, s + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        cout << s[i];
    }
    return 0;
}