P1012题目链接

做题过程

先判断看一看数据范围，$1≤n≤20$，$1≤a_i≤{10^9}$，数组内最大长度只能为 $20$，每个数最大长度为$9$

一开始，能清晰的判断出这题考查的是排序，两两字符串对比他们的首位，如果首位相同继续对比下一个数字。但是后认为实现起来会比较困难。对比选数字拼最大结果的问题

如何选出首位最大的数，于是我们可以使用字符串拼接达到目的

原理

假如我们有 $123759804368450$ 和 $54365789062$两个数字

我们可以先试用前后拼接，先后拼接出

$12375980436845054365789062$ 和 $54365789062123759804368450$

可见，如果是首位更大的数字会更大一些，于是我们可以比较他们的差值，使用类似这个排序的代码进行对两数字排序

1
Arrays.sort(arr,(o1, o2) -> o2.length() - o1.length());

但由于限于长度，$long \ int$类型都无法进行运算，我们可以拿出 $BigInteger$进行高精度的运算

1
2
3
4
5
6
7
8
9
// 排序
Arrays.sort(arr,(o1, o2) -> {
    // 计算两字符串拼接的差值
    BigInteger diff = new BigInteger(o2+o1).subtract(new BigInteger(o1+o2));
    // 判断大小
    // 使用字符串判断正负, intValue() 转化会出现精度上的问题
    // 比如 负号消失
    return diff.toString().startsWith("-") ? -1 : 1;
});
  • 如此判断之后，从左到右输出该字符串组即可。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;

public class P1012 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Throwable {
        // 凑数的
        int n = Integer.parseInt(br.readLine());
        // 用切片快速获取字符串组
        String[] arr = br.readLine().split(" ");

        Arrays.sort(arr,(o1, o2) -> {
            BigInteger diff = new BigInteger(o2+o1).subtract(new BigInteger(o1+o2));
            return diff.toString().startsWith("-") ? -1 : 1;
        });
        // 从左到右输出字符串
        for (String str : arr) {
            pw.print(str);
        }
        pw.flush();
    }
}

总结

要更熟悉字符串的操作，一些技巧