试题编号： 202109-2
试题名称： 非零段划分
时间限制： 1.0s
内存限制： 512.0MB
问题描述：
题目描述
A1,A2,…,An是一个由 n 个自然数（非负整数）组成的数组。我们称其中 Ai,…,Aj 是一个非零段，当且仅当以下条件同时满足：
·1≤i≤j≤n；
·对于任意的整数 k，若 i≤k≤j，则 Ak＞0；
·i=1 或 Ai-1=0；
·j=n 或 Aj+1=0。
下面展示了几个简单的例子：
·A = [3, 1, 2, 0, 0, 2, 0, 4, 5, 0, 2] 中的 4 个非零段依次为 [3, 1, 2]、[2]、[4, 5] 和 [2]；
·A = [2, 3, 1, 4, 5] 仅有 1 个非零段；
·A = [0, 0, 0] 则不含非零段（即非零段个数为 0）。
现在我们可以对数组 A 进行如下操作：任选一个正整数 p，然后将 A 中所有小于 p 的数都变为 0。试选取一个合适的 p，使得数组 A 中的非零段个数达到最大。若输入的 A 所含非零段数已达最大值，可取 p = 1，即不对 A 做任何修改。
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 n。
输入的第二行包含 n 个用空格分隔的自然数 A1, A2, … , An。
输出格式
输出到标准输出。
仅输出一个整数，表示对数组 A 进行操作后，其非零段个数能达到的最大值。
样例1输入
11
3 1 2 0 0 2 0 4 5 0 2
样例1输出
5
样例1解释
p = 2 时，A = [3, 0, 2, 0, 0, 2, 0, 4, 5, 0, 2]，5 个非零段依次为 [3]、[2]、[2]、[4, 5] 和 [2]；此时非零段个数达到最大。
样例2输入
14
5 1 20 10 10 10 10 15 10 20 1 5 10 15
样例2输出
4
样例2解释
p = 12 时，A = [0, 0, 20, 0, 0, 0, 0, 15, 0, 20, 0, 0, 0, 15]，4 个非零段依次为 [20]、[15]、[20] 和 [15]；此时非零段个数达到最大。
样例3输入
3
1 0 0
样例3输出
1
样例3解释
p = 1 时，A = [1, 0, 0]，此时仅有 1 个非零段 [1]，非零段个数达到最大。
样例4输入
3
0 0 0
样例4输出
0
样例4解释
无论 p 取何值，A 都不含有非零段，故非零段个数至多为 0。
子任务
70% 的测试数据满足 n ≤ 1000；
全部的测试数据满足 n≤5×105，且数组 A 中的每一个数均不超过 104。
问题链接：CCF202109-2 非零段划分
问题简述：（略）
问题分析：
这道题用暴力法来解，可以得70分。三分法只是撞大运，虽然也可以得100分。除了索引法，还有一种解法是差分法。差分法和索引法才是正解。其他解法有扫描线法和单调判定法，也是正解。
解法一：三分法
给出的题解程序，当n≤1000时，采用枚举法，结果是没有问题；当n＞1000时，采用3分法求极值的方法，逻辑上是不严密，因为不是单极值问题。
比较一下100分程序和70程序，就可以知道，100分程序的逻辑也是不严密的。当n≤1000时也采用了3分法，只能得70分，似乎说明逻辑不够严密。
解法二：索引法
用向量数组v[]存储各种值所在位置，向量v[i]中存储i值在数组a[]中的位置。向量v可以看作是各种值的下标索引。往往想这样的索引，会使得程序变得稍微难以理解。
开始的时候，把整个A数组看作一段，所有程序中last=1。然后，取p=0,1,2,…,maxa（数组A元素的最大值）取划分数组A。如果a[i]位置置为0，那么如果原先a[i-1]=0并且a[i+1]=0则划分段数减一；如果a[i]位置置为0，那么如果原先a[i-1]0并且a[i+1]0则划分段数加一；其他情况则段数不变。数组book[]用来标记a[i]是否置为0，若book[i]=1则表示a[i]被置为0（操作使之为0）。开始时，数组A的两端置为0，所以程序中需要对数组book[]进行初始化。
变量last表示上一次的划分数，变量t表示在上一次划分的基础上，再进行p变换后的划分数。
这个解法程序虽然是二重循环，其实其时间复杂度是O(N)。
解法三：差分法
借用岛屿情况来分析这个题。考虑p足够大的情况，所有的数都被海水淹没了，只有0个岛屿。然后，海平面逐渐下降，岛屿数量出现变化。每当一个凸峰出现，岛屿数就会多一个；每当一个凹谷出现，原本相邻的两个岛屿就被这个凹谷连在一起了，岛屿数减少一个。使用数组cnt[]，cnt[i] 表示海平面下降到i时，岛屿数量的变化。
差分法是最简洁的解题程序。数组元素d[i]中存储该元素被替换为0时，划分数变化的差分值。最大值则只需要从其前缀和（程序中实际为后缀和）中找出最大值就是所要的结果。
程序代码中，STL算法函数unique()用来去除相邻重复的元素。
语句“a[0] = a[n + 1] = 0;”用来设置边界值，起辅助计算作用，可以简化程序代码。
解法四：扫描线法
给解题程序代码，暂时不解释。
解法五：单调判定法
给解题程序代码，暂时不解释。
程序说明：
三分法+暴力的原始解题程序来自太理陈同学的100分解题程序。这里的解题程序代码是改写过的。
索引法的原始解题程序来自仙客传奇团队的李同学和钱同学的100分解题程序。这里的解题程序代码是改写过的。
差分法的原始解题程序来自仙客传奇团队的隔壁李叟同学的100分解题程序。这里的解题程序代码是改写过的。
参考链接：
CSP 2021-09-2 非零段划分
csp2021-09-2 非零段划分
题记：（略）
100分的C++语言程序（解法五：单调判定法）如下：
/* CCF202109-2 非零段划分 */#include using namespace std;const int N = 500000;int a[N];int main(){ int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int ans = 0, cnt = 1, flag = 1, k; if (n == 1) ans = a[0] ? 1 : 0; else { for (k = 1; k < n; k++) if (a[k] != a[0]) break; if (k == n) ans = a[0] ? 1 : 0; else { map<int, int> m; if (a[k] < a[0]) { m[a[0]]--; flag = 1 - flag; } while (k < n) { if (flag) { while (k < n && a[k - 1] <= a[k]) k++; if (k == n) break; m[a[k - 1]]--; } else { while (k < n && a[k - 1] >= a[k]) k++; if (k == n) break; m[a[k - 1]]++; } flag = 1 - flag; } if (flag) m[a[n - 1]]--; ans = 1; for (auto x : m) { cnt += x.second; ans = max(ans, cnt); } } } printf("%d\n", ans); return 0;}100分的C++语言程序（解法四：扫描线法）如下：
/* CCF202109-2 非零段划分 */#include using namespace std;const int N = 500000;pair<int, int> a[N + 2];int book[N + 1];int main(){ int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i].first); a[i].second = i; } a[0].first = a[n + 1].first = 0; sort(a + 1, a + n + 1); int ans = 0, cnt = 0; memset(book, 0, sizeof book); for (int i = n; i >= 1; i--) { if (a[i].first != a[i + 1].first) ans = max(ans, cnt); int k = a[i].second; if (book[k - 1] && book[k + 1]) cnt--; else if (book[k - 1] == 0 && book[k + 1] == 0) cnt++; book[k] = 1; } printf("%d\n", ans); return 0;}100分的C++语言程序（解法三：差分法）如下：
/* CCF202109-2 非零段划分 */#include 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; n = unique(a, a + n + 2) - a - 1; memset(d, 0, sizeof d); 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]]--; int ans = 0, sum = 0; // 差分前缀和即为答案 for (int i = M; i >= 1; i--) sum += d[i], ans = max(ans, sum); printf("%d\n", ans); return 0;}100分的C++语言程序（解法二：索引法）如下：
/* CCF202109-2 非零段划分 */#include using namespace std;const int N = 500000;const int M = 10000;int a, book[N + 2];vector<int> v[M + 1];int main(){ int n, maxa = 0; scanf("%d",&n); for (int i = 1; i <= n; i++) { scanf("%d",&a); maxa = max(maxa, a); v[a].push_back(i); } int ans = 0; if (v[0].size() != n) { memset(book, 0, sizeof book); book[0] = book[n + 1] = 1; int last = 1; for (int p = 0; p <= maxa; p++) if (v[p].size() != 0) { int t = last; for (int ix = 0; ix < (int)v[p].size(); ix++) { book[v[p][ix]] = 1; if (book[v[p][ix] - 1] && book[v[p][ix] + 1])t--; else if (book[v[p][ix] - 1] == 0 && book[v[p][ix] + 1] == 0) t++; } ans = max(ans, max(last, t)); last = t; } } printf("%d\n", ans); return 0;}100分的C++语言程序（解法一：三分法，集合+三分法+枚举）如下：
/* CCF202109-2 非零段划分 */#include #include using namespace std;const int LR = 50;const int N = 500000 + 1;const int M = 10000 + 1;int n, a[N], s[M];int mycount(int p){ int cnt = 0, flag = 1; for (int i = 1; i <= n; i++) if (flag) { if (a[i] >= p) cnt++, flag = 0; } else { if (a[i] < p) flag = 1; } return cnt;}int main(){ int maxa = 0, ans = 0; memset(s, 0, sizeof s); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; maxa = max(maxa, a[i]); s[a[i]] = 1; } int scnt = 0; for (int i = 1; i <= M; i++) if (s[i]) s[scnt++] = i; int l = 0, r = scnt - 1; ans = max(mycount(s[l++]), mycount(s[r--])); while (r - l > LR) { int ll = l + (r - l) / 3; int rr = r - (r - l) / 3; if (mycount(s[ll]) < mycount(s[rr])) l = ll; else r = rr; } for(int i = l; i <= r; i++) ans = max(ans, mycount(s[i])); cout << ans << endl; return 0;}100分的C++语言程序（三分法+枚举）如下：
/* CCF202109-2 非零段划分 */#include using namespace std;const int N = 500000 + 1;int n, a[N];int mycount(int p){ int cnt = 0, flag = 1; for (int i = 1; i <= n; i++) if (flag) { if (a[i] >= p) cnt++, flag = 0; } else { if (a[i] < p) flag = 1; } return cnt;}int main(){ int maxa = 0, ans = 0; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; maxa = max(maxa, a[i]); } if (n <= 1000) for (int i = 1; i <= maxa; i++) ans = max(ans, mycount(i)); else { int l = 1, r = maxa; while (r - l > 4) { int ll = l + (r - l + 1) / 3; int rr = r - (r - l + 1) / 3; if (mycount(ll) < mycount(rr)) l = ll; else r = rr; } for(int i = l; i <= r; i++) ans = max(ans, mycount(i)); } cout << ans << endl; return 0;}70分的C++语言程序（三分法）如下：
/* CCF202109-2 非零段划分 */#include #include using namespace std;const int N = 500000 + 1;int n, a[N];int mycount(int p){ int cnt = 0, flag = 1; for (int i = 1; i <= n; i++) if (flag) { if (a[i] >= p) cnt++, flag = 0; } else { if (a[i] < p) flag = 1; } return cnt;}int main(){ int maxa = 0, ans = 0; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; maxa = max(maxa, a[i]); } int l = 1, r = maxa; while (r - l > 4) { int ll = l + (r - l + 1) / 3; int rr = r - (r - l + 1) / 3; if (mycount(ll) < mycount(rr)) l = ll; else r = rr; } for(int i = l; i <= r; i++) ans = max(ans, mycount(i)); cout << ans << endl; return 0;}