题解：P14127 [SCCPC 2021] K-skip Permutation
题意
构造一个长度为 \(n\) 的排列 \(P\)，使得 \(f(P,k)\) 最大。
对于 \(f(P,k)\) 的定义：对于一个 \(n\) 的排列 \(P=p_1,p_2,\cdots,p_n\)，\(f(P,k)\) 表示满足 \(1 \le i <n\) 且 \(p_i+k=p_{i+1}\) 的 \(i\) 的个数。
算法 tag
构造。
数据规模与约定
\(1 \le n,k \le 10^6\)。
题解
核心思路
观察题目可以发现，最优的策略是将 \(1\) 到 \(n\) 的数按模 \(k\) 的余数分组。具体来说，对于每个余数 \(r\)，组 \(r\) 包含的数为 \(r,r+k,r+2k,\cdots\)，直到超过 \(n\) 为止。
例如，当 \(k=3,n=7\) 时，分组结果为：
- \(1,4,7\) 满足条件
- \(2,5\) 满足条件
- \(3,6\) 满足条件
注意：每个组内的元素必须从小到大，这样才能满足相邻两个元素的差为 \(k\) 的条件，而且最大化答案。
正确性验证
- 每个组内的元素差为 \(k\)，一个大小为 \(s\) 的组能贡献 \(s-1\) 个满足条件的答案。
- 总满足条件的答案为所有组的 \((s_i-1)\) 之和，即 \(\sum (s_i-1)=n-m\)（\(m\) 为非空组数量），这是理论最大值。
CODE
#include <bits/stdc++.h>
using namespace std;
/*====================*/
using ll=long long;
/*====================*/
#define endl '\n'
/*====================*/
void Solve()
{int n,k;cin>>n>>k;for(int r=1;r<=k;r++) {for(int x=r;x<=n;x+=k) {cout<<x<<" ";}}cout<<endl;
}
/*====================*/
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int T=1;//cin>>T;while(T--)Solve();return 0;
}
注：本文已被 luogu 审核通过至 P14127 题解区