题解 | #最优屏障#

计算每座山作为一个相互监视点间的区间左端点和中间点的的次数（除作为区间右端点外），然后取次数最多的那一个，其左端点即为答案。

#include<bits//stdc++.h>
using namespace std;
long long int Min(long long int a,long long int b)
{
    return a<b?a:b;    
}
int main()
{
 int t,n;
 long long int H[50000];
 scanf("%d",&t);
 for(int x=1;x<=t;x++)
 {
  scanf("%d",&n);
  for(int i=0;i<n;i++) scanf("%lld",&H[i]);
  int flag[50000];
  memset(flag,0,sizeof(flag));
  for(int i=0;i<n-1;i++)
  { 
     int j=i+1;
     long long int max=H[j];
     flag[i]++;
     while(j<n-1&&H[i]>max)
       if(Min(H[i],H[++j])>max){
        for(int a=i;a<j;a++) flag[a]++;
        max=max>H[j]?max:H[j]; 
     }
  }
  int MAX=0,most;
  for(int i=0;i<n-1;i++) if(flag[i]>MAX) {MAX=flag[i];most=i;}
  printf("Case #%d: %d %d\n",x,most+2,flag[most]);
 }
    
    return 0;
}