526互联

Technocup 2022 - Elimination Round 3 B. Array Eversion

发布时间 2023-09-26 17:21:32作者: zsxuan

给一个长度为 \(n\) 的数组。执行一次以下操作：

  • 让 \(x = a_n\) ，然后数组 \(a\) 被分为左右两部分。左部分包含所有 \(\leq x\) 的元素，右部分包含所有 \(> x\) 的元素。且数组整体的原顺序不变。

询问经过多少次操作后，数组不再改变？

\(1 \leq n \leq 2 \cdot 10^5, 1 \leq a_i \leq 10^9\) 。

观察一：数组的变化只取决于 \(a_n\) 。

观察二：每次 \(a_n\) 会更新左边一个更大值。

观察三：当 \(a_n\) 为最大值，不能再操作。

view 
#include <bits/stdc++.h>
typedef long long ll;
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];
	int cnt = 0, mx = a[n];
	for (int i = n; i; --i) if (mx < a[i]) mx = a[i], cnt++;
	std::cout << cnt << '\n';
}
		                
int main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}