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

Sliarae · 2025-05-14 19:53:19 · 题解

对着想了半天，感觉还是打表找规律题。

首先考虑如果要求 A 为排列怎么做。找到一个最小的 n，使得序列 [n, n - 1, \ldots, 1] 的逆序对数 \frac{n(n - 1)}{2} \ge x，然后将数字 v = n - (\frac{n(n - 1)}{2} - x) 交换到位置 A_1。这样可以使得 A 的字典序最小。

现在去掉 A 为排列的性质，显然 n 是不变的。但按上面方法构造 A 会出现问题。比如 x = 7 时答案为 [2, 3, 2, 1, 1]，而前面的方法会求出 [2, 5, 4, 3, 1]。

我们尝试对 A 为排列的构造进行调整，比如 [2, 5, 4, 3, 1]，我们将 A_4 = 3 修改为 1 变成 [2, 5, 4, 1, 1]，发现少了一个逆序对（这里用下标二元组表示）(4, 5)，但又多了一个 (1, 4)，于是总逆序对数不变。最后再对前面进行微调得到 [2, 3, 2, 1, 1]。

可以再尝试几种情况，比如 [2, 6, 5, 4, 3, 2] \rightarrow [2, 4, 3, 2, 1, 1], [3, 6, 5, 4, 2, 1] \rightarrow [3, 3, 2, 2, 1, 1]。可以发现答案形如 [v, \ldots, v + 1, v, v - 1, v - 1, \ldots, 2, 2, 1, 1]。

然后前面其实是 v \le \frac{n}{2} 的情况，v > \frac{n}{2} 是差不多的。比如 [4, 6, 5, 3, 2, 1] \rightarrow [4, 3, 2, 2, 1, 1]。大概就是构造形如 [v, v - 1, \ldots, k + 2, k + 1, k, k, \ldots, 2, 2, 1, 1] 的序列。

#include <iostream>

using namespace std;

int main () {
  cin.tie(0)->sync_with_stdio(0);
  int x, n = 2;
  cin >> x;
  for (; n * (n - 1) / 2 < x; ++n);
  cout << n << '\n';
  int v = 1 + x - (n - 1) * (n - 2) / 2;
  const static int kN = 2e5 + 5; 
  static int a[kN]; 
  a[1] = v;
  if (v <= n / 2) {
    int i = n; 
    for (int j = 1; j < v; i -= 2, ++j) a[i] = a[i - 1] = j; 
    a[i--] = v; 
    for (int j = v + 1; i > 1; --i, ++j) a[i] = j; 
  }
  else {
    for (int i = n, j = 1; i > 1; ++j) {
      if (i - 1 != v - j) a[i] = j, --i;
      a[i] = j, --i;
    } 
  }
  for (int i = 1; i <= n; ++i) cout << a[i] << ' ';
  cout << '\n';
  return 0; 
}