题解: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 题解区