考虑到有 \(|i - j|\),所以肯定是让相邻的一部分在一个团里。
考虑构造出一个最长长度的,后面类似复制几遍即可。
考虑到 \(|k - 1| = k - 1\),且因为 \(a_i\) 为一个排列,差的绝对值至少为 \(1\),所以只考虑两端最长长度也只可能为 \(k\)。
不妨先假设最长长度为 \(k\) 来构造。
那么就相当于要让 \(a_1 = x, a_k = x + 1\)。
那么对于 \(a_2\),\(|k - 1| - |k - 2| = 1\),那么如果 \(|a_k - a_2| - |a_k - a_1| = 1\),就有 \(|k - 1| - |a_k - a_1| = |k - 2| + |a_k - a_2| = k\),这是合法的。
于是便可以考虑令 \(a_2 = a_1 - 1\)。
类似的,令 \(a_{k - 1} = a_k + 1\)。
以此类推,有 \(a_i = a_{i - 1} - 1, a_i = a_{i + 1} + 1\),显然应该找到个临界点让左边的 \(a_i\) 用左边的方式,右边的 \(a_i\) 用右边的方式构造。
考虑到如果选取 \(\lfloor\frac{k}{2}\rfloor + \lceil\frac{k}{2}\rceil = k\),那么这部分最劣的距离为 \(2(\lceil\frac{k}{2}\rceil - 1) \le k + 1 - 2 = k - 1\le k\),合法。
于是按照这个方法构造即可。
时间复杂度 \(O(n)\)。
代码
#include<bits/stdc++.h>
inline void solve() {
int n, k; scanf("%d%d", &n, &k);
for (int l = 1, r; l <= n; l = r + 1) {
r = std::min(l + k - 1, n);
int len = r - l + 1, p = len + 1 >> 1, c0 = l + p - 1, c1 = r;
for (int i = 1; i <= p; i++) printf("%d ", c0--);
for (int i = 1; i <= len - p; i++) printf("%d ", c1--);
}
puts("");
printf("%d\n", (n + k - 1) / k);
for (int l = 1, r, c = 0; l <= n; l = r + 1) {
r = std::min(l + k - 1, n), c++;
for (int i = l; i <= r; i++) printf("%d ", c);
}
puts("");
}
int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}