二分答案，考虑答案是否会大于等于这个mid，显然所有数值分为两类：大于等于mid和小于mid
将n个数转化为01串，如果0和1不相邻，那么答案就是第一个数/最后一个数（一定会相同），考虑有连续两个0/1
否则连续的两个数一定会上升到某一个高度并变为一个数，因此只需要找到最高的一层全部变成0/1时，也就是最靠近中心的连续0/1，那么这个就是答案
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,l,r,a[200005]; 4 int pd(int x,int k){ 5 if ((a[x]>=k)&&(a[x+1]>=k))return 1; 6 if ((a[x]<k)&&(a[x+1]<k))return -1; 7 return 0; 8 } 9 bool check(int k){ 10 for(int i=0;i<n;i++){ 11 if (pd(n-i-1,k))return (pd(n-i-1,k)+1)/2; 12 if (pd(n+i,k))return (pd(n+i,k)+1)/2; 13 } 14 return a[1]>=k; 15 } 16 int main(){ 17 scanf("%d",&n); 18 for(int i=1;i<2*n;i++)scanf("%d",&a[i]); 19 l=1,r=2*n-1; 20 while (l<r){ 21 int mid=(l+r+1>>1); 22 if (check(mid))l=mid; 23 else r=mid-1; 24 } 25 printf("%d",l); 26 }
原文：https://www.cnblogs.com/PYWBKTDA/p/11629255.html
