526互联

Educational Codeforces Round 91 (Rated for Div. 2) A. Three Indices

发布时间 2023-10-15 22:42:09作者: zsxuan

给一个 \(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;
}