题目描述

给定一个大小为 $n$ 的数组 $a$ 和一个整数 $k$。

你可以执行以下操作任意次（0次也行）:

选择一个下标 $i$ 满足 $1\le i\le n-k$，然后交换 $a_i$ 和 $a_{i+k}$。

问是否可以使得数组变为非降序。

输入格式

第一行两个整数 $n,k$。($1\le n\le 10^5,1\le k\le n-1$)

接下来一行 $n$ 个整数，表示 $a_i$。($1\le a_i\le 10^9$)。

输出格式

如果可以，输出"Yes"，否则输出"No"。（输出不包含引号）

样例输入1

5 2
3 4 1 3 4

样例输出1

Yes

样例输入2

5 3
3 4 1 3 4

样例输出2

No

---

思路

将数组$a$的元素按照下标模$k$的值分组，然后在每一组中按照元素的值排序。如果所有的元素都满足非降序的条件，那么就意味着可以通过交换操作使得数组变为非降序。这是因为在每一组中，元素的下标之差都是$k$，所以可以通过交换操作改变它们的相对位置。

首先，定义了一个优先队列的数组hmin，数组的大小为$N$，其中$N$是一个大于$n$的常数。优先队列hmin[i]用于存储所有下标模$k$等于$i$的元素。

然后，从输入中读取$n$和$k$的值，接着读取数组$a$的元素。对于每一个读入的元素$t$，将其放入优先队列hmin[i % k]中，其中$i$是当前元素的下标。

接着，定义了一个变量prev用于存储上一个取出的元素，以及一个标志变量flg用于标记是否所有的元素都满足非降序的条件。

然后，遍历数组$a$的每一个元素。对于下标为$i$的元素，从优先队列hmin[i % k]中取出最小的元素，然后检查这个元素是否大于等于prev。如果不是，那么将flg设置为$0$，并且立即停止遍历。否则，将这个元素赋值给prev，然后继续遍历。

最后，如果flg的值仍然为$1$，那么输出"Yes"，表示可以通过交换操作使得数组变为非降序。否则，输出"No"，表示无法通过交换操作使得数组变为非降序。

---

AC代码

#include <iostream>
#include <queue>
#define AUTHOR "HEX9CF"
using namespace std;const int N = 1e5 + 7;priority_queue<int, vector<int>, greater<int>> hmin[N];int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n, k;cin >> n >> k;for (int i = 0; i <= n; i++) {int t;cin >> t;hmin[i % k].push(t);}int prev;bool flg = 1;for (int i = 0; i <= n; i++) {int t = hmin[i % k].top();hmin[i % k].pop();if (i && t < prev) {flg = 0;break;}prev = t;}if (flg) {cout << "Yes" << endl;} else {cout << "No" << endl;}return 0;
}