C++
分析
当非零段个数达到最大时,p必定可在A[N]中选定,因此利用STL中的set将A去重且排序后得到a,
题中要求每次将小于p的位置置为0,则我们每次遍历A将A=a的位置置为0,
此时p的值就为a+1;即可依次求出各个状态时非零段个数.
暴力 70分代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
const int N = 5e5 + 10;
int n, A[N], res;
set<int>a;
int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> A[i];
a.insert(A[i]);//去重排序
}
for(auto i = a.begin(); i != a.end(); i ++){
int ans = 0;
for(int j = 1; j <= n; j ++){//每次暴力遍历数组A
if(*i == A[j]) A[j] = 0;
if(!A[j - 1] && A[j]) ans ++;
}
res = max(res, ans);
}
cout << res;
return 0;
}
分析
暴力得70分后,我们会发现下面这段暴力遍历A的代码,很多遍历是无效的.
for(int j = 1; j <= n; j ++){//每次暴力遍历数组A
if(*i == A[j]) A[j] = 0;
if(!A[j - 1] && A[j]) ans ++;
}
因此,我们想办法优化这个遍历过程,可能就能AC了.
这时我们可以用STL中的vector把一开始A中的每个数的下标存起来,
暴力遍历的过程就可以直接用下标访问的方法代替,从而提高效率.
优化后 100分代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
using namespace std;
const int N = 5e5 + 10;
int n, A[N];
set<int>a;
vector<int>s[N];
int main(){
cin >> n;
int ans = 0, res = 0;
for(int i = 1; i <= n; i ++){
cin >> A[i];
s[A[i]].push_back(i);//存储A中每一个数所出现的位置,以便后续直接访问,从而提高效率.
a.insert(A[i]);//去重排序
if(!A[i - 1] && A[i]) ans ++; //当前位置不为0,且上一位置为0,则非零段+1.
}
for(auto i = a.begin(); i != a.end(); i ++){
for(auto j = s[*i].begin(); j != s[*i].end(); j ++){
if(A[*j - 1] && A[*j + 1] && A[*j]) ans ++;//当前位置及其左右都不为0时,非零段+1.
if(!A[*j - 1] && !A[*j + 1] && A[*j]) ans --;//当前位置不为0,且左右为0,非零段-1.
//当前位置为0或不为0,且左右其中一个(或两个)为0,则非零段不变.
A[*j] = 0;
}
res = max(res, ans);
}
cout << res;
return 0;
}