526互联

CSP 202109-2 非零段划分

发布时间 2023-09-14 09:01:13作者: catting123

题目

C++代码

// 202109-2 非零段划分
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 500010;
const int M = 10010;

int a[N], d[M]; // d[i] 为差分数组
bool c[N];
int n, ans, sum;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    a[0] = a[n + 1] = 0;

    n = unique(a, a + n + 2) - a - 1; // unique去除相邻两个重复元素

    for (int i = 1; i < n; i++) {
        if (a[i-1] < a[i] && a[i] > a[i+1]) {
            d[a[i]]++;
        } else if (a[i-1] > a[i] && a[i] < a[i+1]) {
            d[a[i]]--;
        }
    }

    for (int i = 10000; i >= 1; i--) {
        sum += d[i];
        ans = max(ans, sum);
    }

    printf("%d\n", ans);
    return 0;
}