CF482A Diverse Permutation 题解

分析

话说这题为啥要写题解啊？

因为，我最最最最不擅长的构造题，我最最最最期望的「构造作战」，还是要从水题开始攻克吧。

如何构造 $k$ 种差值呢？

这样构造的差值是 $k,k-1,k-2 \cdots$，那么就可以用 $k+1$ 个数字构造出 $[1,k]$ 中所有的差值。

照这样，维护两个指针 $i=1$ 与 $j=k+1$，这样就确定了一个差值。然后让 $i+1$，$j-1$，又确定一个差值，知道 $i \ge j$。如果这样操作之后出现了 $i=j$ 的情况，那么就说明 $k+1$ 是个奇数，进而 $k$ 是偶数。由于一轮确定 2 个数，假设进行了 $t$ 轮，那么就有了 $2t$ 个数确定了 $2t-1$ 个差值，这显然是个奇数。所以还要再补上一个 $i$。

那么后面的怎么搞呢？我们只用到了 $[1,k+1]$ 的数，且一定全部用完并包含 1 这个差值。那么只要顺序输出 $[k+2,n]$ 所有的数就能满足条件。

CODE

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N=1e5+5;
4
int n, k, ans[N];
5
int main() {
6
    scanf("%d%d",&n,&k);
7
    int i=1, j=i+k;
8
    while(1) {
9
        printf("%d %d ",i++,j--);
10
        if(i>=j) {
11
            if(i==j) printf("%d ",i);
12
            break;
13
        }
14
    }
15
    for(int i=k+2;i<=n;++i) printf("%d%c",i," \n"[i==n]);
16
}