题目
思路
第一种思路:按照表面题意,枚举p,处理数组后进行计数:
复杂度 ∈ O ( n ⋅ m ) 复杂度 \in O(n \cdot m) 复杂度∈O(n⋅m)
第二种思路:把数组看成一个二维的山形图,先将相邻的水平线段转化成点(对数组unique),再对每个子结构进行考虑
复杂度 ∈ O ( m i n ( n , m ) ) 复杂度 \in O(\;min(n, m)\;) 复杂度∈O(min(n,m))
具体思路:
- 先unique,把相邻相等的元素去重
- 分为三种子结构,考虑水面暴露其顶点后,其对非零段数量的贡献,记录在cnt[ ]数组中
2.1. A形结构,只要“水面”暴露出顶点开始,对非零段数量的贡献为+1
2.2. V形结构,只要“水面”暴露出顶点开始,对非零段数量的贡献为-1把原本分离的两段合并了
2.3 / \ 形结构,我们把中间点看作“顶点”,暴露顶点前后贡献不变 - 遍历 p f o r [ M − 1 , 1 ] p \; for \;[M-1, 1] pfor[M−1,1] 模拟水面降低,维护一个 s u m sum sum 作为计数器
TLE代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int main()
{int n;cin >> n;int amax = 0;for(int i = 1; i <= n; i++) cin >> a[i], amax = max(amax, a[i]);int ans = 0;for(int p = 1; p <= amax; p++){int cnt = 0; int last = 0;for(int i = 1; i <= n; i++){int x = a[i];if(a[i] < p) x = 0;if(x && !last) cnt++;last = x;}ans = max(ans, cnt);}cout << ans;return 0;
}
正确代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10, M = 1e4+10;
int cnt[M], a[N];
int main()
{int n;cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];n = unique(a+1, a+n+1) - (a+1);a[0] = 0, a[n+1] = 0;for(int i = 1; i <= n; i++){int x = a[i-1], y = a[i], z = a[i+1];if(x < y && z < y) cnt[y]++;if(x > y && z > y) cnt[y]--;}int ans = 0; int sum = 0;for(int i = M - 1; i >= 1; i--){sum += cnt[i];ans = max(ans, sum);}cout << ans;return 0;
}