计算每座山作为一个相互监视点间的区间左端点和中间点的的次数(除作为区间右端点外),然后取次数最多的那一个,其左端点即为答案。
#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;
}
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;
}