51nod 1281 山峰和旗子 （二分试探法）

题目链接

https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1281

题意

题解

求出山峰点放入数组中。
然后二分枚举旗子数。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e4+7;int a[maxn];
vector<int> V;bool check(int x)
{if(V.size()==0) return false;int cnt=1,tar=V[0]+x;if(cnt==x) return true;for(int i=1;i<V.size();i++){if(cnt==x) return true;if(V[i]>=tar){cnt++;tar=V[i]+x;}if(cnt==x) return true;}return false;
}int main()
{int n;while(~scanf("%d",&n)){V.clear();for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=2;i<n;i++)if(a[i]>a[i-1] && a[i]>a[i+1])V.push_back(i);int l=1,r=maxn,ans=0;while(l<=r){int mid=(l+r)>>1;if(check(mid)) l=mid+1,ans=mid;else r=mid-1;}printf("%d\n",ans);}return 0;
}