将选中了的和没被选中的数区别出来;
用一个长度为k的区间扫描整个序列, 找出区间中没有被选中的数的和的最大值;(双指针算法实现)
最后用这个最大值加上所有被选中的数字就做出来啦!(#^.^#)
这题双指针算法的模型和这道题目的很像: https://www.acwing.com/problem/content/801/
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, k;
int a[N];
bool st[N];
int main()
{
cin >> n >> k;
for(int i = 1;i <= n;i ++) cin >> a[i];
for(int i = 1;i <= n;i ++) cin >> st[i];
LL maxn = 0, sum = 0;
for(int i = 1, j = 1;i <= n;i ++)
{
if(i - j + 1 > k)
{
if(!st[j]) sum -= a[j];
j ++;
}
if(!st[i]) sum += a[i];
maxn = max(maxn, sum);
}
LL res = 0;
for(int i = 1;i <= n;i ++) if(st[i]) res += a[i];
cout << maxn + res << endl;
return 0;
}
前缀和写法
b为选中数的前缀和, c为未选中数的前缀和;
找到区间为k的未选中数的和最大值, 再与所有选中的数相加;
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, k;
LL a[N], b[N], c[N];
bool st[N];
int main()
{
cin >> n >> k;
for(int i = 1;i <= n;i ++) cin >> a[i];
for(int i = 1;i <= n;i ++) cin >> st[i];
for(int i = 1;i <= n;i ++)
if(st[i]) b[i] = a[i];
else c[i] = a[i];
for(int i = 1;i <= n;i ++) b[i] += b[i - 1], c[i] += c[i - 1];
LL res = 0;
for(int i = 1;i + k - 1 <= n;i ++)
{
int j = i + k - 1;
res = max(res, c[j] - c[i - 1]);
}
cout << res + b[n] << endl;
return 0;
}
qaq..哪位佬能帮我看看哪错了?
大佬可以帮我看看哪错了吗?调半天没找到原因呀
int main()
{
int n,k;
int tmp = 0;
int curValue = 0;
cin >> n >>k;
int a = (int)malloc(sizeof(int)n);
int b = (int)malloc(sizeof(int)n);
for(int i = 0; i < n; i)
{
cin >> tmp;
a[i] = tmp;
}
for(int i = 0; i < n; i)
{
cin >> tmp;
b[i] = tmp;
if(tmp==1){
curValue += a[i];
}
}
int maxVal = 0;
int curVal = 0;
for(int i = 0; i <= k-1; i++)
{
if(b[i]==0){
curVal+=a[i];
}
}
maxVal = curVal;
}