526互联

Codeforces Round 677 (Div. 3) C. Dominant Piranha

发布时间 2023-10-13 18:56:44作者: zsxuan

有 \(n\) 只水虎鱼在水族馆，大小为 \(a_1, a_2, \cdots, a_n\) 。

一只水虎鱼被称为是主导的，当它可以吃掉水族馆中其他所有水虎鱼。其他水虎鱼不会有任何行动。

一只水虎鱼只可以吃掉当前与它相邻并且体型严格比它小的水虎鱼。当大小为 \(x\) 的水虎鱼吃掉大小为 \(y\) 的水虎鱼时，主导与的大小会变为 \(x + y\) 。

给出 \(a_1, a_2, \cdots, a_n\) ，询问是否存在一只主导鱼。并输出任一只可能的主导鱼的初始位置。

当所有水虎鱼的大小相等，显然不存在一只主导鱼。
否则存在一个位置 \(x\) 。满足\(a_x\) 最大，且 \(a_{x -1}\) 或 \(a_{x + 1}\) \(< a_x\) 。当 \(a_x\) 吃掉比它更小的一只鱼后，相邻的鱼永远 \(< a_x\) 。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n; std::cin>> n;
	std::vector<int> a(n+1);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	if (std::count(a.begin() + 1, a.end(), a[1]) == n) std::cout << -1 << "\n";
	else {
		int mx = *std::max_element(a.begin() + 1, a.end());
		for (int i = 2; i < n; i++) {
			if (a[i] == mx) {
				if (a[i - 1] < a[i] || a[i + 1] < a[i]) {
					std::cout << i << "\n";
					return;
				}
			}
		}
	}
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}