题目描述
使用双指针来解决区间问题
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
O(n)
参考文献
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e5 +10;
int main(){
long n,k,d[N],s[N];
long maxM =0,left,right,sum = 0;
long res = 0;
cin>>n>>k;
for(int i = 1;i<=n;i++) cin>>d[i];
for(int i = 1;i<=n;i++) cin>>s[i];//对应数组中每一个数的状态
for(int i =1;i<=n;i++){//将最终结果累加起来;
if(s[i]){
res += d[i];
}
}
//这里我是想在循环中使用i作为左值,但是发现这样的化会有很多的边界条件需要考虑,所以以后都采用i作为右值来计算就可以了
// for(int i =1;i<=k;i++){
// if(!s[i]) sum += d[i];
// }
// for(int i = 1;i<=n;i++){//i作为左边界,寻找一个最大的右边界使得在这个范围里得到的下标为0的数的和最大
// int left = i;right = left+k;
// if(right <= n)
// {
// if(!s[right]) sum+=d[right];
// if(!s[left]) sum-= d[left];
// }
// maxM = max(sum,maxM);
// }
for(int i =1;i<=n;i++){
if(!s[i]) sum+=d[i]; //其中i就表示滑动区间的right值,如果right下标为0那么就是可加的
if(i>k &&!s[i-k]) sum -= d[i-k]; //如果当前的滑动区间right值已经比题目中给的k值大了就,开始对lift值进行判断
maxM = max(sum,maxM); //对于每次的求值取区间的最大值
}
cout<<res + maxM;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla