给一个 \(n\) 个整数的排列 \(p_1, p_2, \cdots, p_n\) ,需要找到三个数 \(i, j, k\) 满足:
- \(1 \leq i < j < k \leq n\)
- \(p_i < p_j\) , \(p_j < p_k\)
否则回答不可能。
\(key\) :若存在上述 \(i, j, k\) ,则存在 \(x\) 满足 \(p_{x - 1} < p_{x}, p_{x} > p_{x + 1}\) 。
证明:
已知任意 \(p_i\) 不同,假设 \(i, j, k\) 存在。
- 若 \(p_{j + 1} > p_j\) 不妨让 \(j = j + 1\) ,若 \(p_{j + 1} < p_j\) 不妨让 \(k = j + 1\) 。
- 若 \(p_{j - 1} > p_j\) 不妨让 \(j = j - 1\) ,若 \(p_{j - 1} < p_j\) 不妨让 \(i = j - 1\) 。
于是存在 \(x\) 满足 \(p_{x - 1} < p_{x}, p_{x} > p_{x + 1}\) 。
view
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n; std::cin >> n;
std::vector<int> a(n+1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
for (int i = 2; i < n; i++) {
if (a[i - 1] < a[i] && a[i + 1] < a[i]) {
std::cout << "YES\n";
std::cout << i - 1 << ' ' << i << ' ' << i + 1 << '\n';
return;
}
}
std::cout << "NO\n";
}
int main() {
int _ = 1; std::cin >> _;
while (_--) { solve(); }
return 0;
}