codeforce 599C Day at the Beach

Bi表示第i个块，那么就是说B_{i max} ≤ B_{i+1 min}，又因为B_{i min} ≤ B_{i max}，

因此只要判断前缀的最大值是否小于等于后缀。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 1e5+1;
int h[maxn], n;
int mn[maxn];

//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", h+i);
    }
    mn[n-1] = h[n-1];
    for(int i = n-2; i >= 0; i--){
        mn[i] = min(mn[i+1],h[i]);
    }
    int mx = h[0], ans = 1;
    for(int i = 1; i < n; i++){
        if(mx <= mn[i]) ans++;
        mx = max(h[i], mx);
    }
    printf("%d
", ans);
    return 0;
}