#119. 最大整数 题解

题目传送门

更新日志

• 2023-05-26 17:20 文章完成
• 2023-05-30 15:22 文章审核通过
• 2023-07-01 16:04 修改了代码

题目知识点

字符串+贪心

题意说明

设有n个正整数（$n<20$），将它们连接成一排，组成一个最大的多位整数。（题目简介明了，一看就是出题人懒得写题目背景）

问题分析

拿到这道题，首先自然会想到大的字符串应该排在前面，因为如果A与B是两个由数字字符构成的字符串，且 $A>B$ ，一般情况下有 $A+B$$<$$B+A$ 的情况。如 $A=$ ' $121$ ', $B=$ ' $12$ ',则 $A+B=$ ' $12112$ ', $B+A=$' $12121$ ',所以 $A+B$$<$$B+A$ 。
为了解决这些问题，根据题意引进另一种字符串比较方法，将 $A+B$ 与 $B+A$ 相比较，如果前者大于后者，则认为 $A>B$ 。按这一定义将所有的数字字符串从大到小排序后连接起来所得到的数字字符串即是这个问题的解。排序时先将所有字符串中的最大值选出来存在数组的第一个元素中，再从第二到最后的一个元素中最大的字符串选出来存在第二个元素中，直到最后的两个元素中选出最大的字符串存在数组的倒数第二个元素为止。

代码+解释

// #119. 最大整数
// code by:st20250113
#include <bits/stdc++.h> //伟大的万能头文件
using namespace std;
int n;
struct num {
    int a, b;
} c[21];
int a(int x, int y) // x^y
{
    if (y == 0) {
        return 1;
    }
    if (y == 1) {
        return x;
    }
    int z;
    z = a(x, y / 2); // 这里可以和上面合并写作：int z=a(x,y/2);
    if (y % 2 == 1) {
        return z * z * x;
    } else {
        return z * z;
    }
}
bool abc(num x, num y) {
    int w, p;
    w = x.a * y.b + y.a;
    p = y.a * x.b + x.a;
    return w > p;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> c[i].a;
        c[i].b = 0;
        int x;
        x = c[i].a; // 这里可以和上面合并写作：int x=c[i].a;
        while (x) {
            x /= 10;
            c[i].b++;
        }
        c[i].b = a(10, c[i].b);
    }
    sort(c + 1, c + n + 1, abc);
    for (int i = 1; i <= n; i++) {
        cout << c[i].a;
    }
    return 0; // 华丽结束
}
//QYC最帅

欢迎大家指出错误