ABC254C K Swap

题面

题目描述

给出一个长为 $n$ 的数列 $a_1, a_2, \cdots, a_n$。再给一个整数 $k$。

每次可以选一个下标 $i$（$1 \le i \le n - k$），将 $a_i$ 和 $a_{i + k}$ 交换。

问能否通过交换让数列 $a$ 成为升序（任意 $a_i \le a_{i +1}$）？

输入格式

输入包括两行，第一行有 $2$ 个正整数 $n, k$。

第二行有 $n$ 个正整数 $a_1, a_2, \cdots, a_n$。

输出格式

如果可以通过交换变成升序，输出 $\texttt{Yes}$。不能变成升序，输出 $\texttt{No}$。

说明/提示

$2 \le n \le 2 \times 10^5$；$1 \le k \le n - 1$；$1 \le a_i \le 10^9$。

题解

根据本题的数据范围可得，解题不能够承受dfs交换的暴力搜索。

本题的关键之处在于只能交换$a_i$和等距离之外的$a_{i + k}$。我们可以把这个条件转换为：一些相隔等距离（$k$）的数字间两两可以交换，相当于这些数字之间可以在原位上按照任何顺序排列。

这时的思路第一步就很清晰明显了：

将原数列分为$k$组，每组的第$i + 1$项和第$i$项保证在原数组中下标差为$k$，第$i$组形如$a_i,a_{k + i},a_{2k + i}\cdots$

这一步看起来复杂，但实际的实现过程就是在每一步输入的过程中用取模的逻辑把每一项分配进每一组中。这里项数不定，为了少建一点$cur$指针变量，这里推荐使用vector。

vector<int> v[N];
for (int i = 1;i <= n;i++) {
	cin >> a[i];
	v[i % k].push_back(a[i]); // 用取模自动分配，第k组分配到下标0
}

接下来，按照我们前文的推导可知，每一组内的数任意交换位置，这个操作在$a$数组全局上都是合法的。那么，我们如何借助这个自由排列的优势尽力为原数组维护不下降的状态呢？

在任何一组内，我们无法顾及到其他组的情况，但因为只是组内排列（不是选数放入原数组，即每个数据无论大小都要排进去），所以我们不用顾及其他组的选择，只需要每个组做到对原数组在小数组局部方面不对大数组全局方面构成影响，采用一点贪心的思路，那么得到的排序就是尽力排的最优解。

这一步难在考虑如何进行贪心并对其进行证明，代码在经过思考后，已经显而易见了。

for (int i = 0;i < k;i++) sort(v[i].begin(),v[i].end());

接下来我们在完成局部排序后，要开始验证是否可以最终组合成不下降序列了。这里我们只需要“化零为整”，将每一个小组按照顺序穿插起来就行了。这里非常容易混淆数组的下标和指针的数值（因为第k组被安排到了下标0上）。我们可以用$b$（动态）数组记录存放数据。

const int N = 2e5 + 5;
int a[N],b[N],curv = -1,curb = 0;
for (int i = 1;i <= n;i++) {
	if (i % k == 1) curv++;
	b[++curb] = v[i % k][curv];
}

最后的验证环节就非常简单了。附上完整代码：

#include<iostream>
#include<vector>
using namespace std;

const int N = 2e5 + 5;
int a[N],b[N],curv = -1,curb = 0;
vector<int> v[N];

int main() {
	int n,k;
	cin >> n >> k;
	for (int i = 1;i <= n;i++) {
		cin >> a[i];
		v[i % k].push_back(a[i]);
	}
	for (int i = 0;i < k;i++) sort(v[i].begin(),v[i].end());
	for (int i = 1;i <= n;i++) {
		if (i % k == 1) curv++;
		b[++curb] = v[i % k][curv];
	}
	bool flag = true;
	for (int i = 2;i <= n;i++) flag &= (b[i] >= b[i - 1]);
	cout << (flag ? "Yes" : "No") << endl;
	return 0;
}