题解：P12386 [蓝桥杯 2023 省 Python B] 混乱的数组

第一个绿题最优解！

## 题意
我们需要构造一个尽可能短的数组 $A$，使得其中恰好有 $x$ 对逆序对（$i < j$ 且 $A_i > A_j$），且字典序最小。核心问题在于如何通过数学构造满足条件的数组，并证明其最优性。

## 思路
我们来确定数组长度 $n$，因为逆序对的最大数量为完全逆序数组的逆序对数，即 $\frac{n(n-1)}{2}$。因此，最小的 $n$ 需满足：
$$\frac{n(n-1)}{2} \geq x$$
   解得：
$$n = \left\lceil \frac{1 + \sqrt{1 + 8x}}{2} \right\rceil$$

若 $x = \frac{n(n-1)}{2}$，则数组为完全逆序排列，例如 $[n, n-1, \dots, 1]$。

若 $x < \frac{n(n-1)}{2}$，则需分两部分构造数组：

1. 前半部分：通过两两递增的方式生成部分逆序对。例如，形如 $[a_1, a_1, a_2, a_2, \dots]$ 的序列，每对重复元素贡献 1 个逆序对。  
2. 后半部分：以降序排列补充剩余逆序对。

设中间分割点为 $mid$，其值由以下公式确定：
$$mid = \begin{cases}
   2 \cdot (x - \frac{(n-1)(n-2)}{2}) & \text{if } x - \frac{(n-1)(n-2)}{2} \leq \frac{n-1}{2} \\
   2 \cdot (\frac{n(n-1)}{2} - x) & \text{otherwise}
   \end{cases}$$

字典序最小的要求意味着数组应尽可能靠前的位置出现较小值，所以我们先构造初始数组，再将数组反转以使得较小的元素尽可能靠前。

## Code
```cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    LL x;
    cin >> x;

LL s = sqrt(1 + 8 * x);
    if (s * s < 1 + 8 * x) s++;
    LL n = (1 + s) / 2;
    while (n * (n - 1) / 2 < x) n++;

LL Cn2 = n * (n - 1) / 2;
    LL Cnn2 = (n - 1) * (n - 2) / 2;

LL mid;
    if (x - Cnn2 <= (n - 1) / 2) {
        mid = 2 * (x - Cnn2);
    } else {
        mid = 2 * (Cn2 - x);
    }

LL ans[n + 1];
    for (int i = 1; i <= mid; ++i) {
        ans[i] = (i + 1) / 2;
    }
    for (int i = mid + 1; i <= n; ++i) {
        ans[i] = mid / 2 + (i - mid);
    }
    
    ans[n] = x - Cnn2 + 1;

reverse(ans + 1, ans + n + 1);

cout << n << '\n';
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << ' ';
    }

return 0;
}
```