P6181 [USACO10OPEN]Mountain Watching S 题解

Wy_x · 2022-10-03 10:58:46 · 题解

题目传送门

更好的阅读体验？

题意：

• 给定 n 和 n 个数，求最宽的山的宽度（其实就是最长单峰子序列， 但我不会）。

数据范围：

做法：

• 注意：直接爆搜会超时！！！

• 建数组 h 存放山脉信息，最大值 maxn 存最宽山的宽度；

• 每次从 i 开始搜索，定义 l 和 r , l 记录向左搜到的位置，r 记录向右搜到的位置（注意搜到边界 1，n 时的特判），搜索方法题目中给出来了

• 如果现在搜出的山的宽度 > maxn 则更新 maxn；

• 如果现在搜出的山的宽度 \leq maxn 则不更新 maxn；

• 最后输出 maxn。

• 注：三目运算符表达式1?表达式2:表达式3，若表达式1值为真返回 表达式2，否则返回表达式3。

考虑优化：

若某次搜出的山的宽度为 n，那就没有继续搜索下去的必要了，maxn=n，以后再搜出来的山的宽度肯定 \leq n，就不会再更新 maxn 的值，可以直接跳出循环。不优化最后一个点会TLE。

• 弱化版P1893 山峰暸望可以不优化。

代码

#include<bits/stdc++.h>
using namespace std;
int n,maxn=-1,h[100050];
//maxn存最大值，初始化最小   
int ma(int x,int y) { return x>y?x:y; }
//自己写的判断最大值的函数  
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++)
    {
        int l=i,r=i;
        //向左搜索 left，向右搜索 right 
        while(h[l-1]<=h[l]&&l-1>=1)  l--;
        while(h[r+1]<=h[r]&&r+1<=n)  r++;
        maxn=ma(r-l+1,maxn);
        //或 maxn=max(r-l+1,maxn); 
        //自己写函数只是为了加快速度  
        if(r-l+1==n) break;
        //优化： 
        //不优化会TLE 
        //若某次搜索出山的宽度为n, 
        //那这座山的宽度肯定是最大的  
        //那就没有搜下去的必要了 
        //直接跳出循环  
    }
    cout<<maxn;
    //输出最大值  
    return 0;
}