题目
http://118.190.20.162/view.page?gpid=T130
题目图片
思路一：暴力法(70分)
我的做法是：先做一个判断非零段的函数，然后依次去p值，将数组中小于p的值置0，将改变后的数组导到一个新的数组中，调用判断函数判断非零段，然后取max值。
然后，我判断非零段的方法也很简单，碰到非零的就+1，然后把非零的全部遍历完，再碰到非零的还这样，以此类推……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int arr[N],n;
int ss[N];
int judge(int num[], int n) {
int cnt = 0;
for (int i = 0; i < n; i++) {
if (num[i] != 0) {
cnt++;
while (num[i] != 0) i++;
}
}
return cnt;
}
int maxn(int num[], int n) {
int maxn = -1;
for (int i = 0; i < n; i++) {
if (num[i] > maxn) maxn = num[i];
}
return maxn;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int maxnn = maxn(arr, n);
int cnt = 0,p=0;
for (int i = 1; i <= maxnn; i++) {
for (int j = 0; j < n; j++) {
if (arr[j] < i) ss[j] = 0;
else ss[j] = arr[j];
}
p=judge(ss,n);
cnt=max(p,cnt);
}
cout << cnt;
return 0;
}
|
思路二：前缀和+差分（100分）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <iostream>
using namespace std;
const int N = 1e6;
int dif[N], a[N];
int n;
void add(int l, int r) { dif[l]++, dif[r + 1]--; }
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
if (a[i - 1] < a[i]) {
add(a[i - 1] + 1, a[i]);
}
}
int maxn = 0, pre = 0;
for (int p = 1; p < 1e4; p++) {
pre += dif[p];
maxn = max(maxn, pre);
}
cout << maxn;
return 0;
}
|
理解
这个要用到前缀和以及差分的思想，在这里写的话就显得篇幅太长了，另写博文描述。请看下面的文章：
https://www.cnblogs.com/yongcheng137blogs/p/15412952.html
总结
- 在函数内部定义过大的函数时会爆栈，我第一次写的时候（暴力法），每次改变p值时都在循环内定义一个新数组来存储改变后的数组。然后程序也没有报错，但是运行时就是自己中断了，问了大佬才知道原来在还是内部定义太大的数组时会爆栈，所以以后尽量把函数定义在main函数前。
- 加深理解前缀和，了解了差分这种算法。我发现最近几年CCF的第二题好像都用到了前缀和，要多多练习掌握！
