AcWing 3493. 最大的和
原题链接
简单
作者:
云之端i
,
2021-05-15 15:34:23
,
所有人可见
,
阅读 225
两种方法
法1:双指针
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, k;
int a[N];
bool b[N];
LL sum1 = 0;
LL sum2 = 0,maxSum2 = 0;
int main(){
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++){
scanf("%d",&a[i]);
}
for(int i = 0; i < n; i++){
scanf("%d",&b[i]);
if(b[i]) sum1 += a[i];
}
for(int i = 0,j = 0; i < n; i++){
if(!b[i]) sum2 += a[i];
while(j < i && i - j + 1 > k){
if(!b[j]) sum2 -= a[j];
j++;
}
maxSum2 = max(maxSum2, sum2);
}
printf("%lld",maxSum2 + sum1);
return 0;
}
法2:一个前缀和
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
LL presum[N];
int a[N], b[N];
int n, k;
LL sum1 = 0,sum2 = 0, maxSum2 = 0;
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
cin >> b[i];
if(b[i]) sum1 += a[i];
presum[i] = presum[i - 1] + a[i] * (1 - b[i]);
}
// for(int i = 1; i <= n ; i++){
// cout<<presum[i]<<" ";
// }
for(int i = k; i <= n; i++){
sum2 = presum[i] - presum[i - k];
maxSum2 = max(maxSum2, sum2);
}
cout<<maxSum2 + sum1;
return 0;
}