洛谷P1970 花匠

传送门

首先可以知道，如果一个序列是连续上升的，那么只需要取这一个序列中最高的元素即可，因为取其它的不能保证大于后面的.连续下降的序列同理.而这些恰好就是波峰和波谷.

所以遇到 $ j $ 比之前的 $ i $ 大，那么在 $ j $ 之后找比 $ j $ 小的最小的 $ k $ ,反过来也是一样.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define re register
using namespace std ;
const int maxn = 1000005 ;

inline int read () {
    int f = 1 , x = 0 ;
    char ch = getchar () ;
    while(ch > '9' || ch < '0') {if(ch == '-')  f = -1 ; ch = getchar () ;}
    while(ch >= '0' && ch <= '9')  {x = (x << 1) + (x << 3) + ch - '0' ; ch = getchar () ;}
    return x * f ;
}

int n , h[maxn] ;
int flag , ans = 1 ;

int main () {
    n = read () ;
    for(re int i = 1 ; i <= n ; ++ i)  h[i] = read () ;
    for(re int i = 1 ; i < n ; ++ i) {
        if(h[i] < h[i + 1] && flag != 1) {
            flag = 1 ;
            ans ++ ;
        }
        if(h[i] > h[i + 1] && flag != 2) {
            flag = 2 ;
            ans ++ ;
        }
    }
    printf("%d\n" , ans ) ;
    return 0 ;
}

洛谷P1970 花匠

原文：https://www.cnblogs.com/Stephen-F/p/10656689.html