C. Manhattan Permutations

曼哈顿排列的值是 $\sum_{i = 1}^{n} | p_{i} - i |$ , $p$ 是排列。

给定曼哈顿排列值，要求构造出这个排列。

Solution

每次都能想到正确思路，但是就是写不出来，总感觉差点什么...

构造

首先讨论不可能的情况：

显然 $k$ 是奇数不可能
$k$ 太大超过这个排列最大能到的数据也不可能

最大的数据是： $1, 2, 3 \dots, n$ 和 $n, n - 1, \dots 1$ 这个两个排列的差的情况。

即 $\sum_{i = 1}^{n} | n - 2 \times i + 1 | = \sum_{i = 1}^{⌊ \frac{n + 1}{2} ⌋} (n - 2 \times i + 1) + \sum_{i = ⌊ \frac{n + 1}{2} ⌋ + 1}^{n} (2 \times i - n - 1)$

拆开化简后最大值即为 $$2\times\lfloor{\frac{n+1}{2}}\rfloor(n-\lfloor{\frac{n+1}{2}}\rfloor)$$
再讨论符合条件的情况如何构造：

当 $1$ 和 $n$ 交换时，可以构造 $2 (n - 1)$ 的值， $2$ 和 $n - 1$ 交换可以构造 $2 (n - 3)$ 这样的值，...，一共可以构造：

$\sum_{i = 1}^{n} 2 (n + 1 - 2 \times i) = MAX$ 的值。所以这个情况是一定能够构造出所有可能的。

若 $k < 2 (n - 1)$ 时： $1$ 就不和 $n$ 交换，和 $n - 1, n - 2 \dots$ 其中一个交换，
能构造的值 $v = 2 (n - 3) - 4 k (k = 0, 1, 2 \dots) \cap v \geq 0$

若 $k \geq 2 (n - 1)$ 时： $1$ 和 $n$ 交换，进行下一轮，能构造的值为 $2 (n - 1)$ 。

后面的同理，容易知道能够构造所有合理值。

Example

例如：
$n = 5, k = 6$ ，若 1 和 5 交换可以构造 $2 (n - 1) = 8 > 6$ ，所以 1 和 $n - 1 = 4$ 交换 $(1, 4) - (4, 1)$ 得到 6.

$n = 5, k = 10$ ，若 1 和 5 交换可以构造 $2 (n - 1) = 8 < 10$ ，所以 1 和 5 需要交换，剩下 2。
下一轮若 2 和 4 交换可以构造 $2 (n - 3) = 4 > 2$ ，所以不交换，选择之前的值 $n - 2, n - 3 \dots$ ，可以知道 2 和 3 交换后恰好构造出 2，得到 2。

#define int long long
void solve() {
    int n, k;cin >> n >> k;
    int m = (n + 1) / 2;
    int p = 2 * m * (n - m);
    if (k & 1 || k > p) {
        cout << "NO\n";return;
    }
    cout << "YES\n";
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)a[i] = i;
    k /= 2;
    for (int i = 1;k > 0;i++) {
        if (k < n - 2 * i + 1) {
            swap(a[i], a[i + k]);k = 0;
        } else {
            swap(a[i], a[n - i + 1]);
            k -= n - 2 * i + 1;
        }
    }
    for (int i = 1;i <= n;i++)cout << a[i] << " \n"[i == n];
}