2021-9-2非零段划分(前缀和最简解法)(c/c++实测满分)-创新互联
总结
当前文章:2021-9-2非零段划分(前缀和最简解法)(c/c++实测满分)-创新互联
当前链接:http://myzitong.com/article/cdjseg.html
区间原地划分时可以观察相邻元素之间的大小关系是否与划分有关。前缀和与差分实现单位时间内区间数值整体加1。(ccf-csp第二题真的很爱考前缀和。)
创新互联从2013年开始,先为泊头等服务建站,泊头等地企业,进行企业商务咨询服务。为泊头企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。前缀和详解:
一、题目要求题目描述
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
Data
样例1输出
5
二、我的解法(70)#includeusing namespace std;
const int N=1e5;
int a[N],b[N];
bool st[N];//该值是否曾经出现过
int main(){
int n;
cin>>n;
int num=0;
for(int i=0;i=b[i]){
res++;
//cout<=b[i]) j++;//移动到下一个0
}
}
if(res>ans) ans=res;
}
cout<
分析:
注意到 p 只有取到了数组中的值非零段的划分才会发生变化,依此减少了外层循环的循环次数,但是找不到p的取值和数组之间的关系,双重循环还是超时。万万没想到,又考了前缀和。
三、满分解法#includeusing namespace std;
const int N=5e5+5,M=1e4;//N一定要开够了,不开够还是超时
int a[N],b[M];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>a[i-1]){//a[i-1]到a[i]-1段的p都能构成新的非零段
b[a[i]]--;//处理差分数组以实现区间整体+1
b[a[i-1]]++;
}
}
int ans=0;
for(int i=1;i<=M;i++){
b[i]+=b[i-1];//求前缀和
if(b[i]>ans) ans=b[i];//记录前缀和数组中的大值
}
cout<
分析:
当a[i]>a[i-1]时,只要p取到区间a[i-1]到a[i]-1中的值,都能构成一个新的非零段。这就是p与数组的关系,根据这个关系利用前缀和与差分实现单位时间内区间数值整体加1,将双重循环改进至单层,降低计算时间。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
当前文章:2021-9-2非零段划分(前缀和最简解法)(c/c++实测满分)-创新互联
当前链接:http://myzitong.com/article/cdjseg.html