【ETOJ P1023】同鱼系题解（数学+取余）

本文主要是介绍【ETOJ P1023】同鱼系题解（数学+取余），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

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

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

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

输入格式

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

接下来一行 $n$ 个整数，表示 $a_i$ 。( $\leq a_i \leq 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;
}