文章目录
- 代码解释
- C++
- 总结
本题链接：202109-2 非零段划分
本博客给出本题截图：
代码解释
应各位博友的需求，写一下本题思路，本题用到了 前缀和 以及 差分 的思维，且这两个算法是近几次考试中的第二题突破口，没有了解的同学一定要先去了解完其原理再看本篇题解。
好，那么我们接下来去分析这道题目，题目的要求其实就是选择一个数，然后让数组中所有小于该数的值变为0，然后统计数组中的非零段数目的最大值，我们怎么去设计这个差分思路：我们的 p 假设从一个特别大的值开始取，一直让p -- 那么当p == a[i](max) 即当p等于数组a中的最大值时，会出现第一个非零段，这里我们把出现的非零段称为一个凸点，那么按照这个思路继续让p --，当我们每出现一个凸点的时候，我们的非零段就会多一个；接下来去思考什么情况会让非零段减少呢？即当两个凸点中间出现一个小的数字，这里举一个例子，设数组a为[6 4 6]，那么当p == 5的时候，数组a为[6 0 6]，显然是有两个凸点(均为6)，即非零段的个数为2。那么此时我们按照先前思路，执行p --， 那么这个时候p == 4，数组a变为[6 4 6]，非零段的个数变为1，即当两个大数之间出现一个小数的话，我们的非零段个数就会变少，我在这里称这个点为凹点。
综上所述，我们得到结论：每当一个凸点出现的时候，非零段的个数就会增加，否则非零段的个数就会减少，我们用数组b去表示这个过程，b[i]即表示当p的值等于i的时候，非零段个数的变化，最后我们的最大值只需要求一次前缀和(求的过程中不断取max)即可。
C++
#include <iostream> #include <algorithm> using namespace std; const int N = 500010; int a[N], b[N]; int main() { int n; cin >> n; for(int i = 1; i <= n; i ++ ) { cin >> a[i]; if(a[i] > a[i - 1]) { b[a[i - 1]] ++; b[a[i]] --; } } int ans = 0, t = 0; for(int i = 0;i < N;i ++ ) { t += b[i]; ans = max(ans, t); } cout << ans << endl; return 0; }
用去重函数unique去除重复的元素版：
#include <iostream> #include <algorithm> using namespace std; const int N = 10010, M = 500010; int a[M], b[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> a[i]; int m = unique(a, a + n + 2) - a; for (int i = 1; i < m; i ++ ) { if (a[i] > a[i - 1] && a[i] > a[i + 1]) b[a[i]] ++; if (a[i] < a[i - 1] && a[i] < a[i + 1]) b[a[i]] --; } int ans = 0, t = 0; for (int i = N; i; i -- ) { t += b[i]; ans = max(ans, t); } cout << ans << endl; return 0; }
总结
标准的一道前缀和 + 差分的题目（这几次考试第二题好像都设计前缀和的思想了
前缀和
差分
