拼数

Nowcoder-16783-拼数

分析

把字符串按照字典序由大到小排序后拼接的贪心算法是错误的，如98、9与321、32。

正确的思路：微扰（邻项交换）。

实现

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

const int N = 30;
string a[N];

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

int main () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    sort(a + 1, a + n + 1, cmp);

    if (a[1] == "0") {
        cout << "0";
    } else {
        for (int i = 1; i <= n; ++ i) cout << a[i];
    }
    return 0;
}