题意简述

给定一个 $1$ 到 $n$ 的排列 $p_1,p_2,\dots,p_n$。
构造数组 $a_i$，每个 $a_i$ 要么等于 $p_i$，要么等于 $2n - p_i$。
求构造出的 $a$ 中最少的逆序对数量。

逆序对：$i<j$ 且 $a_i > a_j$。

关键观察

对于原排列中的数 $p_i$，它的两种可能取值是：

• $x_i = p_i$
• $y_i = 2n - p_i$

注意 $p_i$ 取值范围 $1 \dots n$，因此 $2n-p_i$ 取值范围 $n \dots 2n-1$。

也就是说，第一种取值在 $[1, n]$，第二种取值在 $[n, 2n-1]$。

重要性质：
所有 $x_i$ 互不相同（因为是排列），所有 $y_i$ 也互不相同，并且 $x_i < y_i$，且 $x_i + y_i = 2n$。
另外，$y_i = 2n - x_i$，所以若 $x_i < x_j$，则 $y_i > y_j$。

贪心策略

我们想让逆序对尽可能少，即希望数组 $a$ 尽量非降序。

从左到右处理，每次选择 $x_i$ 或 $y_i$，尽可能让当前值 $\ge$ 上一个选的值。

设上一个选的值为 $\text{last}$。

当前两个候选：

• $x_i = p_i$
• $y_i = 2n - p_i$

情况分类

1. 两个候选都 $\ge \text{last}$
   选较小的那个（$x_i$），有利于后面。

2. 只有一个候选 $\ge \text{last}$
   选那个可行的。

3. 两个候选都 $< \text{last}$
   无论选哪个都会产生逆序对（相对上一个位置）。
   选较小的那个，减小对后续的影响。

为什么贪心正确？

因为 $x_i$ 与 $y_i$ 的和固定为 $2n$，且大小分布对称。
如果上一个值已经很大（比如接近 $2n$），那么选 $y_i$ 可能更差；如果上一个值较小，选 $x_i$ 更优。
这个贪心实际上是在维护一个尽可能小的“当前最大值”，从而最小化未来逆序对数。
可以证明，不存在一个局部选择会让全局更优，因为逆序对只与相邻的相对顺序有关，局部最优不会破坏全局最优（类似最小化上升序列的逆序对，是单调决策问题）。

算法步骤

1. 初始化 $\text{last} = -1$（表示还没选）。
2. 对 $i = 1$ 到 $n$：
   • $x = p_i$
   • $y = 2n - p_i$
   • 如果 $\text{last} = -1$：选 $\min(x, y)$
   • 否则：
     • 如果 $x \ge \text{last}$ 且 $y \ge \text{last}$：选 $\min(x, y)$
     • 否则如果 $x \ge \text{last}$：选 $x$
     • 否则如果 $y \ge \text{last}$：选 $y$
     • 否则：选 $\min(x, y)$
   • 更新 $\text{last} = \text{选的值}$
3. 最后统计构造出的 $a$ 数组的逆序对（$O(n^2)$ 或 $O(n \log n)$ 树状数组，因为 $n \le 5000$，$O(n^2)$ 可行）。

复杂度

• 时间：$O(n^2)$ 每个测试（逆序对统计），总 $n$ 和 $\le 5000$，可通过。
• 空间：$O(n)$

标程（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> p(n);
        for (int i = 0; i < n; i++) cin >> p[i];
        
        vector<int> a(n);
        int last = -1;
        for (int i = 0; i < n; i++) {
            int x = p[i];
            int y = 2 * n - p[i];
            if (last == -1) {
                a[i] = min(x, y);
            } else {
                if (x >= last && y >= last) {
                    a[i] = min(x, y);
                } else if (x >= last) {
                    a[i] = x;
                } else if (y >= last) {
                    a[i] = y;
                } else {
                    a[i] = min(x, y);
                }
            }
            last = a[i];
        }
        
        int inv = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (a[i] > a[j]) inv++;
            }
        }
        cout << inv << "\n";
    }
    return 0;
}

样例验证

以题目第一个样例：

2
2 1

• $i=1$：$x=2, y=2*2-2=2$，选 $2$，last=2
• $i=2$：$x=1, y=3$，$x < last$ 但 $y \ge last$，选 $y=3$ $a=[2,3]$，逆序对 $0$ ✅

第二个样例：

3
2 1 3

• $i=1$：$x=2, y=4$，last=-1，选 $2$
• $i=2$：$x=1, y=5$，$x < last$（1<2），$y \ge last$（5≥2），选 $5$
• $i=3$：$x=3, y=3$，$3 \ge 5?$ 否，$3 \ge 5?$ 否，选 $\min(3,3)=3$（实际只有3） $a=[2,5,3]$
  逆序对：(5,3) → 1 ✅

这样贪心 + 直接统计逆序对就能得到正确的最小逆序对数。
如果 $n$ 更大（比如 $2\times10^5$），则需要用树状数组优化逆序对统计。