Burnling's Blog
0%

CF1978C Manhattan Permutations

发表于 更新于 分类于 ，

题意简述

给定整数 $n$ 和 $k$，找一个长度为 $n$ 的排列 $p$，使得其曼哈顿值等于 $k$。

曼哈顿值定义为 $|p_1 - 1| + |p_2 - 2| + \ldots + |p_n - n|$。

如果存在这样的排列，输出 “Yes” 并给出排列；否则，输出 “No”。

思路分析

首先考虑什么情况下存在这样的排列。

容易想到，长度为 $n$ 的排列的曼哈顿值是有上限的，当 $n$ 个数倒序排列时，曼哈顿值取到上限

观察曼哈顿值的上限，如果将 $n^2-1$ 看成 $(n+1)(n-1)$ ，那么无论 $n$ 的奇偶性，曼哈顿值均可以看成 $\dfrac{1}{2}$ 乘上两个偶数，结果必定为偶数。

由于任意一种排列可以由另一种排列通过若干次将某一对元素交换位置来得到，所以考虑交换任两个元素对曼哈顿值的影响。

这两个元素的奇偶性有相同和不同两种情况。

  • 若这两个元素的奇偶性相同，那么交换前后，两个位置对曼哈顿值的贡献的奇偶性不变。
  • 若这两个元素的奇偶性不同，那么交换前后，两个位置对曼哈顿值的贡献的奇偶性均相反，总贡献的奇偶性仍不变。

综合以上结论，容易想到，曼哈顿值一定为偶数。

接下来考虑如何构造这个数列。

曼哈顿值的下限为 $0$ —— 当 $n$ 个数升序排列时。

那么我们其实可以考虑从这个升序数列开始，通过一步步交换来增加曼哈顿值至 $k$。

易知在这种情况下，交换第 $i$ 个和第 $j$ 个元素，对曼哈顿值的贡献为 $2|i-j|$。

我们不需要考虑交换重复元素，因为头尾每对元素交换一次即可得到曼哈顿值的上限。

接下来从大到小尝试增加曼哈顿值即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;

const int maxN = 3e5 + 10;
int A[maxN];

inline void solve(){
    int N;
    long long K;
    scanf("%d%lld",&N,&K);
    
    for(int i = 1;i<=N;i++) A[i] = i;
    
    long long ma = 1ll * N * N - (N & 1);
    if((K & 1) || (K > ma)){
        printf("NO\n");
        return;
    }
    
    int l = 1,r = N;
    while(l < r && K > 0){
        if(K >= 2ll * (r - l)){
            K -= 2ll * (r - l);
            swap(A[l],A[r]);
            l++,r--;
        }else r--;
    }
    
    printf("YES\n");
    for(int i = 1;i<=N;i++) printf("%d ",A[i]);
    printf("\n");


}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}