🎈 原创

洛谷P1012 [NOIP1998 提高组] 拼数

题目描述

设有 nn 个正整数 a_1 \dots a_na1…a**n，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 nn。

第二行有 nn 个整数，表示给出的 nn 个整数 a_ia**i。

输出格式

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

输入输出样例

输入 #1

3
13 312 343

输出 #1

34331213

输入 #2

4
7 13 4 246

输出 #2

7424613

说明/提示

对于全部的测试点，保证 1 \leq n \leq 201≤n≤20，1 \leq a_i \leq 10^91≤a**i≤109。

---

题目有点脑筋急转的意思，刚开始看到有点无从下手，看了题解后才发现这题目很巧妙。几个数字组成一个最大的数字，就相当于结果的字符串，字典序最大，这样一来就可以用排序做了。

STL的比较函数也很有意思

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

理解上还是有点难的，但是想同后就觉得真的太妙了。

#include <iostream>
#include <algorithm>
using namespace std;

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

int main(int argc, const char *argv[])
{
    int N;
    cin >> N;
    string S[N];
    for(int i = 0; i < N; i++)
        cin >> S[i];
    sort(S, S + N, cmp);
    for(int i = 0; i < N; i++)
        cout << S[i];


    return 0;
}