2020-05-18 — 习题训练一F

VJ

F - Nastya and Door

 题意：把一个门扔到连着的n座山上，门如果掉到山峰上就会断掉成两半。

　　某座山的高度比左右的两座山都要高就叫山峰。

　　现在给出n座山的高度a[i]，求长度为k的区间内峰值最多为多少，并输出这个区间的左端点（区间需要将峰的左边和右边都包括）。

解题思路：先在[2,k-1]区间求出峰的个数，然后遍历[i,i+k-1]区间峰的个数，求出最大峰值。

ac代码：

#include<iostream>
using namespace std;
int a[200005];
int main(){
	int tt,n,k,i,j,p,l,max,q,m;
	cin>>tt;
	while(tt--){
		cin>>n>>k;
		for(i=1;i<=n;i++){
			cin>>a[i];
		}
		m=k;
		p=0;
		for(i=2;i<m;i++){
			if(a[i]>a[i+1]&&a[i]>a[i-1]){
				p++;//计算区间中峰的个数 
			}
		}
		l=2;
		max=p;
		q=1;
		for(i=m;i<n;i++,l++){
			if(a[i]>a[i+1]&&a[i]>a[i-1]){
				p++;//从尾向右延伸 
			}
			if(a[l]>a[l+1]&&a[l]>a[l-1]&&p){
				p--;//从头向右延伸 
			}
			if(p>max){
				max=p;
				q=l;
			}
		}
		cout<<max+1<<" "<<q<<endl;
	}
	return 0;
}