题解 - ARC144C K Derangement

背景：本人是打表也瞪不出规律，看题解区都是找规律大神，发一篇比较有确定性的解法。

题意简述

找到字典序最小的长度为 $n$ 的排列 $a$，满足 $\forall 1\le i\le n$，$|a_i-i|\ge k$。$n$、$k$ 给定，$2\le n\le 3\times 10^5$，$1\le k\le n$。无解输出 -1。

解析

无解是容易判的：$2k>n$。考虑构造一组字典序不一定最小的可行解：$\{k+1,k+2,\ldots,n,1,2,\ldots,k\}$。那么无解也就显然：第 $n-k$ 位的 $n$ 和第 $n-k+1$ 位的 $1$ 相邻的情景不存在，也就是 $n-k+1-1<k$，即 $2k>n$。

来，减小这个排列的字典序：$\{k+1,k+2,\ldots,n,1,2,\ldots,k\}$。

我希望把 $1$ 提前。我们第一次在点 $k+1$ 处可以选 $1$，这以后的每一处都可以选 $1$。但是 $k+1$ 以后还能不能选 $2k+1$？

意思就是，在前面一大段的 $i$ 我们都选择 $a_i=k+i$。能不能把最后 $\{1,2,\ldots,k\}$ 的头 $1$ 先在前面输出，而在最后放上点 $2k+1$？

如果可以，我们就放，否则，就不放。

这点启发我们想到在逐位考虑 $a_i$ 时维护一个最小的值 $v$，它在 $j<i$ 的 $a_j$ 中没有出现过。如果它可以在 $a_i$ 处出现并且 $i+k$ 可以延迟出现，也就是 $v\le i-k\land i+k\le n-k$，我们输出 $v$，延迟出现 $i+k$。否则我们继续延迟 $v$，输出 $i+k$。

最后把剩余未出现的数升序输出即可。

时间复杂度：$1\sim n$ 逐位考虑 $a_i$，$v$ 移动 $n$ 次，时间为 $O(n)$。

代码

int main() {
  int N(0), K(0);
  cin >> N >> K;
  if (2 * K - 1 >= N) {
    cout << -1 << endl;
    return 0;
  }
  vector<bool> vis(N);
  int id(0);
  for (int i(0); i != N - K; ++i) {
    if (i + K <= N - 1 - K && id != N && id <= i - K) {
      cout << id + 1 << ' ';
      vis[id] = true;
      while (id != N && vis[id]) ++id;
    } else {
      cout << i + K + 1 << ' ';
      vis[i + K] = true;
    }
  }
  while (id != N) {
      cout << id + 1 << ' ';
      vis[id] = true;
      while (id != N && vis[id]) ++id;
  }
  cout << endl;
  return 0;
}