本文主要是介绍1495B - Let‘s Go Hiking 博弈,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
原题链接
学习博客:某大佬的分析
#include <bits/stdc++.h>using namespace std;
//https://blog.csdn.net/donname/article/details/114660119
const int maxn=2e5+5;
int v[maxn],l[maxn],r[maxn],maxlen,cnt,top;
int main()
{int n;cin>>n;l[0]=r[n+1]=v[0]=v[n+1]=0;for(int i=1; i<=n; i++){cin>>v[i];if(v[i]>v[i-1]){l[i]=l[i-1]+1;}elsel[i]=1;}for(int i=n; i>0; i--){if(v[i]>v[i+1])r[i]=r[i+1]+1;elser[i]=1;}for(int i=1;i<=n;i++){ //选出峰顶 这个时候不要判断左右两边的长度!!if(maxlen<l[i]||maxlen<r[i]){maxlen=max(l[i],r[i]);top=i;cnt=1;}else if(maxlen==l[i]||maxlen==r[i]){//峰顶不唯一cnt++;}}///只有 x选在峰顶 左右两边都是等长的奇数长度的下坡时 才能赢///如果是奇数长度且最长的 但只有一侧满足还是赢不了if(l[top]==r[top] && maxlen&1 &&cnt==1){cout<<1<<endl;}else cout<<0<<endl;return 0;
}
这篇关于1495B - Let‘s Go Hiking 博弈的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!