【非零段划分 / 2】

本文主要是介绍【非零段划分 / 2】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

---

思路

第一种思路：按照表面题意，枚举p，处理数组后进行计数： $复杂度\in O(n\cdot m)$

第二种思路：把数组看成一个二维的山形图，先将相邻的水平线段转化成点（对数组unique），再对每个子结构进行考虑 $复杂度\in O(min(n,m))$

具体思路：

1. 先unique，把相邻相等的元素去重
2. 分为三种子结构，考虑水面暴露其顶点后，其对非零段数量的贡献，记录在cnt[ ]数组中
   2.1. A形结构，只要“水面”暴露出顶点开始，对非零段数量的贡献为+1
   2.2. V形结构，只要“水面”暴露出顶点开始，对非零段数量的贡献为-1 把原本分离的两段合并了
   2.3 / \ 形结构，我们把中间点看作“顶点”，暴露顶点前后贡献不变
3. 遍历 $pfor[M-1,1]$ 模拟水面降低，维护一个 $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;
}

这篇关于【非零段划分 / 2】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---