借用岛屿情况来分析这个题。考虑p足够大的情况,所有的数都被海水淹没了,只有 0 个岛屿。然后,海平面逐渐下降,岛屿数量出现变化。每当一个凸峰出现,岛屿数就会多一个;每当一个凹谷出现,原本相邻的两个岛屿就被这个凹谷连在一起了,岛屿数减少一个。使用数组cnt[]
,cnt[i]
表示海平面下降到i时,岛屿数量的变化。
差分法是最简洁的解题程序。数组元素d[i]
中存储该元素被替换为0
时,划分数变化的差分值。最大值则只需要从其前缀和(程序中实际为后缀和)中找出最大值就是所要的结果。
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 500000;
const int M = 10000;
int a[N+2], d[M+1];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
a[0] = a[n+1] = 0;
// unique 去除相邻重复的元素,并把他们移动到末尾
// n 为相邻不重复时的数组长度,从0到n,不包括n
n = unique(a, a+n+2)-a;
memset(d, 0, sizeof d);
for (int i = 1; i < n-1; 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]]--;
}
}
int ans = 0, sum = 0; //差分前缀和即为答案
for (int i = M; i >= 1; i--){
sum += d[i], ans = max(ans, sum);
}
cout << ans << endl;
return 0;
}
标签:int,岛屿,差分法,C++,非零段,202109,ans,CCF
From: https://www.cnblogs.com/understanding-friends/p/16630372.html