AcWing 3493. 最大的和
原题链接
简单
作者:
不幸到吃土
,
2025-01-11 00:31:44
,
所有人可见
,
阅读 1
//共通思路:先求出可选元素的和,再枚举并比较长度为k的区间内:不可选元素的和,二者相加得出结果
-----------------------------------------------------------------------------
//双指针:设长度为k的区间(j,i),每次移动都判断当前枚举元素是否可选:若不可选,则加上;若可选,则无视
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
LL a[N];
int st[N]; //表示各元素的可选状态
int main(){
int n,k;
cin >> n >> k;
for(int i=0;i<n;i++){
cin >> a[i];
}
for(int i=0;i<n;i++){
cin >> st[i];
}
LL res = 0;
for(int i=0;i<n;i++){
if(st[i])
res += a[i];
}
LL ans = 0 , temp = 0;
for(int i=0,j=0;i<n;i++){ //找到"不可选元素之和最大"的区间
if(!st[i])
temp += a[i];
if(i >= k){ //注意!由于下标从0开始,故"i==k"时:已经满足k的长度
j = i-k; //j指向"长度为k的区间"左端点
if(!st[j])
temp -= a[j]; //区间滑动,减去左端点的值
}
ans = max(ans,temp);
}
cout << res+ans << endl;
return 0;
}
-----------------------------------------------------------------------------
//前缀和:对可选元素重赋值为0,此时原数组仅剩不可选元素,接着计算并比较各区间的总和
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
LL s[N]; //表示前缀和
int st[N]; //表示各元素的可选状态
int main(){
int n,k;
cin >> n >> k;
for(int i=1;i<=n;i++){
cin >> s[i];
}
for(int i=1;i<=n;i++){
cin >> st[i];
}
LL res = 0; //储存可选元素的和
for(int i=1;i<=n;i++){
if(st[i]){
res += s[i];
s[i] = 0; //将可选元素重赋值为0,避免影响后续前缀和的计算
}
s[i] += s[i-1];
}
LL ans = 0; //储存不可选元素的和
for(int i=1;i<=n;i++){
int j = i+k-1; //指向"长度为k的区间"右端点
if(j <= n){
LL temp = s[j] - s[i-1];
ans = max(ans,temp);
}
}
cout << res+ans << endl;
return 0;
}