上海计算机学会2023年12月月赛C++乙组T4擦除序列
发布时间
阅读量：
阅读量
擦除序列
内存限制: 256 Mb时间限制: 1000 ms
题目描述
黑板上有 n 个数字，小爱每一次会擦除其中的某个数字，直至所有数字被擦完为止。
每一轮擦除一个数字后，小爱想知道剩下未被擦除的所有数字中，最大连续子段和的值。（在选择最大连续子段和时，不能包含任何被擦除的位置）
输入格式
输入共三行：
第一行：一个正整数n，表示原有数字个数
第二行：n个正整数a1,a2,...,an，分别表示原序列的值
第三行：n个正整数p1,p2,...,pn，表示每次被擦除数字的位置
输出格式
输出共n个数字，分别表示每一轮擦除后，剩下的最大子段和的值，以空格隔开
数据范围
- 对于 30% 的数据，满足 1≤n≤10^2。
- 对于 60% 的数据，满足 1≤n≤10^4
- 对于 100% 的数据，满足 1≤n≤105，1≤ai≤109。
样例数据
输入:
5
1 2 3 4 5
3 5 2 4 1
输出:
9 4 4 1 0
说明:
第1轮：删除第3个数字，得 1 2 X 4 5，此时最大子段和为4+5
第2轮：删除第5个数字，得 1 2 X 4 X，此时最大子段和为4
第3轮：删除第2个数字，得 1 X X 4 X，此时最大子段和为4
第4轮：删除第4个数字，得 1 X X X X，此时最大子段和为1
第5轮：删除第1个数字，得 X X X X X，此时最大子段和为0
解析：使用倒序，最后一个子段和为0，然后从最后擦除的数字开始添加，使用并查集维护子段和，依次找出最大子段和，
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int p[100005];//擦除位置
int a[100005];//原数
int fa[100005];//并查集中的爸爸
long long sum[100005];//维护并查集的和
long long ans[100005];//答案
int b[100005];//从空数组逐步恢复擦除到a数组
int fin(int x){//并查集-找爸爸
if (fa[x]==x) return x;
return fa[x]=fin(fa[x]);
}
void uni(int x,int y){//并查集-合并
int xx=fin(x);
int yy=fin(y);
if (xx!=yy){
fa[yy]=xx;
sum[xx]+=sum[yy];
}
}
int main() {
cin >> n;
for(int i=1;i<=n;i++){
cin>>a[i];
fa[i]=i;//默认爸爸是自己
sum[i]=a[i];//家族和默认是自己
}
for(int i=1;i<=n;i++){
cin>>p[i];
}
long long m=0;//当前最大值
for(int i=n;i>=1;i--){
ans[i]=m;//答案为恢复第i次擦除前的最大值
b[p[i]]=a[p[i]];//p[i]归位
if (b[p[i]-1]>0){//左边有数
uni(p[i],p[i]-1);//把左边合并进来
}
if (b[p[i]+1]>0){//右边有数
uni(p[i],p[i]+1);//把右边合并进来
}
m=max(m,sum[p[i]]);//取最大值
}
for(int i=1;i<=n;i++){//输出答案
cout<<ans[i]<<" ";
}
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~