原題鏈接： https://codeforces.com/contest/1433/problem/C

測試樣例

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

Note

The first test case of the example is described in the problem statement.

In the second test case of the example, there are no dominant piranhas in the aquarium.

In the third test case of the example, the fourth piranha can firstly eat the piranha to the left and the aquarium becomes [4,4,5,4], then it can eat any other piranha in the aquarium.

題意： 在一個魚缸中有$n$條食人魚，它們從$1$到$n$依次編號排列，其中尺寸為$a_i$，有這樣的規則，若食人魚的尺寸大于旁邊的一條食人魚的尺寸，那么這條食人魚就可以吃了它并尺寸$+1$。請你找到一個優勢食人魚。（即經過一系列操作，這條食人魚是最終活下來的食人魚。）

解題思路： 這道題千萬別被樣例騙了。我們首先要知道什么時候無解，是不是當所有食人魚尺寸都相同時無解，那么其他情況是不是都有解呢？當然是，我們總能證明可以不斷使得一條尺寸最大的食人魚逐漸吃了其他的所有食人魚。那么我們關鍵要找到這一條食人魚。 那么為了答案的正確性，即通解，我們肯定是讓強者更強，試想：我們如果讓原先最大尺寸的食人魚再吃一條，它是不是要比其它的所有食人魚都要大了？那么結果是不是就出來了？我們只要找到一條最大尺寸的食人魚且它可以吃掉旁邊的任意一只食人魚即可。那么遍歷判斷即可得出答案。

AC代碼

/* *郵箱：unique_powerhouse@qq.com *blog:https://me.csdn.net/hzf0701 *注：文章若有任何問題請私信我或評論區留言，謝謝支持。 * */ #include<bits/stdc++.h> //POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i為循環變量，a為初始值，n為界限值，遞增 #define per(i,a,n) for (int i=a;i>=n;i--)//i為循環變量， a為初始值，n為界限值，遞減。 #define pb push_back #define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define fi first #define se second #define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//無窮大 const int maxn = 3e5+2;//最大值。 typedef long long ll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<int, int> pii; //*******************************分割線，以上為自定義代碼模板***************************************//int t,n; ll a[maxn]; int main(){//freopen("in.txt", "r", stdin);//提交的時候要注釋掉IOS;while(cin>>t){while(t--){cin>>n;rep(i,1,n){cin>>a[i];}ll maxx=a[1];int ans=1;//統計是不是所有的元素值相同。rep(i,2,n){maxx=max(maxx,a[i]);if(a[i]==a[1])ans++;}if(ans==n){cout<<-1<<endl;continue;}//接下來遍歷。rep(i,1,n){//對邊緣進行判斷。if(i==1&&a[i]==maxx&&a[i+1]<maxx){cout<<i<<endl;break;}else if(i==n&&a[i]==maxx&&a[i-1]<maxx){cout<<i<<endl;break;}else if(i!=1&&i!=n&&a[i]==maxx&&(a[i-1]<maxx||a[i+1]<maxx)){cout<<i<<endl;break;}}}}return 0; }

總結

以上是生活随笔為你收集整理的C. Dominant Piranha（思维） Codeforces Round #677 (Div. 3)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。