Dominant Piranha
There are n piranhas with sizes a1,a2,…,an in the aquarium. Piranhas are numbered from left to right in order they live in the aquarium.
Scientists of the Berland State University want to find if there is dominant piranha in the aquarium. The piranha is called dominant if it can eat all the other piranhas in the aquarium (except itself, of course). Other piranhas will do nothing while the dominant piranha will eat them.
Because the aquarium is pretty narrow and long, the piranha can eat only one of the adjacent piranhas during one move. Piranha can do as many moves as it needs (or as it can). More precisely:
The piranha i can eat the piranha i−1 if the piranha i−1 exists and ai−1<ai.
The piranha i can eat the piranha i+1 if the piranha i+1 exists and ai+1<ai.
When the piranha i eats some piranha, its size increases by one (ai becomes ai+1).
Your task is to find any dominant piranha in the aquarium or determine if there are no such piranhas.
Note that you have to find any (exactly one) dominant piranha, you don’t have to find all of them.
For example, if a=[5,3,4,4,5], then the third piranha can be dominant. Consider the sequence of its moves:
The piranha eats the second piranha and a becomes [5,5–,4,5] (the underlined piranha is our candidate).
The piranha eats the third piranha and a becomes [5,6–,5].
The piranha eats the first piranha and a becomes [7–,5].
The piranha eats the second piranha and a becomes [8–].
You have to answer t independent test cases.
Input
The first line of the input contains one integer t (1≤t≤2⋅104) — the number of test cases. Then t test cases follow.
The first line of the test case contains one integer n (2≤n≤3⋅105) — the number of piranhas in the aquarium. The second line of the test case contains n integers a1,a2,…,an (1≤ai≤109), where ai is the size of the i-th piranha.
It is guaranteed that the sum of n does not exceed 3⋅105 (∑n≤3⋅105).
Output
For each test case, print the answer: -1 if there are no dominant piranhas in the aquarium or index of any dominant piranha otherwise. If there are several answers, you can print any.
Example
Input
6
5
5 3 4 4 5
3
1 1 1
5
4 4 3 4 4
5
5 5 4 3 2
3
1 1 2
5
5 4 3 5 5
Output
3
-1
4
3
3
1
题目的大概思路是寻找最大的鲨鱼，其实满足能找到的条件并不难，只要不全是一种鲨鱼，就肯定不输出-1，那么我们其实只需要找到最大的鲨鱼即可，但同时要注意，并不是所有的最大的鲨鱼都满足条件，最大的鲨鱼旁边还必须有一条比他小的鲨鱼才行。
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
int n,a[301000];
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int judge=1,max=0,position,total=1,count;
scanf("%d",&count);
for(int j=0;j<count;j++)
{
scanf("%d",&a[j]);
if(max<a[j]) //如果有的值更大
{
max=a[j];
position=j;
}
if(j>=1)
{
if(a[j]==a[j-1])//同等的鱼吃不下去
{
total++;//计算同等的鱼的个数
if(judge)//进行累计
position++;//位置右移
}
if(a[j]!=a[j-1])//两条鱼不一样大
judge=0;//停止累计
}
}
if(total==count)//全是一样的鱼
printf("-1\n");
else
printf("%d\n",position+1);
}
return 0;
}
这里比较重要的地方都写了备注，只有一点需要注意，就是第二个if下面的一连串的判断：
及我们从第二条鲨鱼开始判断，如果它和上一条一样大，那么我们就需要将我们的位置记录点向右移动一个，因为这样鲨鱼才可能吃掉下一个鲨鱼并完成成长，total不用说的，就是计数用的，第三个if是判断连续的，如果他们不是连续的，也就是最大鲨鱼旁边有了小鱼，那么我们认为，就不用考虑连续的情况了，judge也就没有了意义，赋值为0即可。
return code;