codeforces Round #677 (Div. 3) 1433C Dominant Piranha

题目链接

题目翻译：

在鱼缸里有n条食人鱼，它们的大小分别是a₁,a₂,…,a_n，并从左到右编号。 伯兰州立大学的科学家想要知道在鱼缸里是否存在占统治地位的鱼。如果一条鱼能吃掉鱼缸里所有的鱼（当然不包括它自己），那么就称这条鱼是占统治地位的鱼。当其它鱼被占统治地位的鱼吃掉时，他们没有反抗的余地。 由于鱼缸特别狭窄而且长，在一次移动中，食人鱼只能吃相邻的两只鱼中的任意一只并且可以移动任意多次。更精确地说：

食人鱼i可以吃食人鱼i-1，如果食人鱼i-1存在并且a_i-1<a_i.食人鱼i可以吃食人鱼i+1，如果食人鱼i+1存在并且a_i+1<a_i.

当食人鱼i吃了一只食人鱼，他的大小就会加一（a_i变成a_i+1）。 你的任务是找到任意一只占统治地位的鱼，或者回答不存在占统治地位的鱼。 注意你只需要找到任意一只占统治地位的鱼，不需要找到所有占统治地位的鱼。 比如，如果a=[5,3,4,4,5]，那么第三只鱼就是占统治地位的鱼：

它先吃掉第二只鱼，然后a就会变成[5,5,4,5] (加粗的就是可能是占统治地位的鱼的候选鱼)再吃掉第三只鱼，a变成[5,6,5]。再吃掉第一只鱼，a变成[7,5]。再吃掉第二只鱼，a变成[8]。

你需要回答t个独立的测试用例。

解题思路：

一开始想的是，是否最大的鱼就是占统治地位的鱼？然后发现如果a=[5,5,5]，那么就不存在占统治地位的鱼。所以需要加上限制条件：且该鱼左、右两只鱼中有一只鱼比该鱼小。这样的话，这条鱼吃掉左边或右边的鱼之后马上就会变成唯一一个最大的鱼，就可以吃掉剩下所有的鱼了。

代码：

#include<iostream> #include<cstring> #include<string> #include<algorithm> #include<vector> #include<map> #include<queue> #include<cstdio> #include<cmath> #define inf 0x3f3f3f3f using namespace std; const int N = 300010; int a[N]; int main(){ // freopen("1.txt","r",stdin); int t,n; cin>>t; while(t--){ cin>>n; int maxn=-1; for(int i=0;i<n;i++){ cin>>a[i]; maxn=max(maxn,a[i]); } int ans=-1,flag; for(int i=0;i<n;i++){ if(a[i]!=maxn) continue; flag=0; if(i-1>=0&&a[i-1]<a[i]||i+1<n&&a[i+1]<a[i]){ flag=1; } if(flag){ ans=i+1; break; } } cout<<ans<<endl; } return 0; }