因为最后的结果要求是严格递增或者严格递减,所以如果原来的序列中存在相同的元素,直接判负
考虑序列中不存在相同元素的情况,可以找到一个长度为m的单调递增或者单调递减的序列,查看其最大值和最小值在已经排序好的序列中的位置的差值是不是等于m。
如果等于m,则说明未排序的序列中,其他n - m个数字,不会出现在这个长度为m的序列中间。-->因为这是一个不存在相同元素的序列。如果不等于m,则相反
基于上述,在原序列中不断寻找长度为m的,升序或者降序的序列,判断这个序列的左右在排序好的序列中,间距是否同样为m。找到一个这样的序列则返回true。找不到这样的序列则是false。
#include <bits/stdc++.h> using namespace std; // 从a中找i和j的位置,判断距离是否等于m int find(vector<int>& a, int i) { int n = a.size(); int l = 0, r = n; while (l < r) { int mid = l + (r - l) / 2; if (a[mid] == i) return mid; else if (a[mid] > i) r = mid; else if (a[mid] < i) l = mid + 1; } return -1; } bool f(vector<int>& a, int i, int j, int m) { int loc1 = find(a, i), loc2 = find(a, j); return abs(loc1 - loc2) + 1 == m; } vector<vector<int>> ff(vector<int>& a, int m, int flag) { // flag = 1表示升序。 vector<vector<int>> ans; int i = 0, j = 1; int n = a.size(); int cnt = 0; while (j != n) { if (flag) if (a[j] > a[j - 1]) cnt++; else cnt = 0, i = j; else if (a[j] < a[j - 1]) cnt++; else cnt = 0, i = j; if (cnt == m - 1) { vector<int> t = {a[i], a[j]}; ans.push_back(t); i++; cnt--; } j++; } return ans; } bool solve() { int n, m; cin >> n >> m; vector<int> a(n), b(n); for (int i = 0; i < n; i++) { cin >> a[i]; b[i] = a[i]; } if (n == 1) return true; sort(b.begin(), b.end()); //存在相同的元素 直接判负 for (int i = 1; i < n; i++) if (b[i] == b[i - 1]) return false; int i = 0, j = 1; int cnt = 0; // 寻找升序的 vector<vector<int>> pairs1 = ff(a, m, 1); // 寻找降序的 vector<vector<int>> pairs2 = ff(a, m, 0); for (auto pair : pairs1) if (f(b, pair[0], pair[1], m)) return true; for (auto pair : pairs2) if (f(b, pair[0], pair[1], m)) return true; return false; } int main() { int n; cin >> n; while (n--) { if (solve()) cout << "YES\n"; else cout << "NO\n"; } }