题解：CF2023A Concatenation of Arrays

zengxuheng · 2025-02-10 20:43:39 · 题解

分析

可以看出，我们有几种排序方式。

第一种：比较两个数组之间相互逆序对大小。

例如：

数组 a1 与 a2 有 cnt1 个逆序对。

数组 a2 与 a1 有 cnt2 个逆序对。

比较 cnt1 与 cnt2 大小来排序。

第二种：看哪个数组有两个数组最大值，那个数组就排在后面。

例如：

数组 a1 元素为 [2,3]，数组 a2 元素为 [1,5]。

因为数组 a2 中有两个数组最大值：5，因此将 a2 排在 a1 后面。

第三种：按和排序。

例如：

数组 a1 元素为 [2,3]，和为 5；数组 a2 元素为 [1,5]，和为 6。

因为 6 > 5，因此将 a2 排在 a1 后面。

证明对错：

第一种：

由于比较两个数组之间相互逆序对大小并不能推向全局，贪心思想必须有传递性，于是废除。

例子：