それならゼロから、いや、ゼロから始めましょう - NYOJ
思路：
遍历：结局是一的就加到cnt中
随后双指针枚举，快指针指向的元素是0则加到cnt，指针间距超过k，若慢指针所指的元素是
0，则cnt减去这个元素，每一轮操作完要res= max；
最后输出res+已经是1的结局契合值
流程：根据题目关键词连续区间来确定用的算法是双指针，考虑双指针的指针移动情况，写出特殊的条件，与数据维护的语句
套路：
1.用双指针滑动窗口就好了，（关键词：连续区间，序列）
此题右指针一直在移动，左指针满足某条件后移动
1. for(int i = 1,j = 1;i <= n;i++){ 2. if(...)j++; 3. }
也有不满足某条件时，右指针移动，满足某条件时左指针移动
1. for(int i = 1,j = 1;i <= m;i++){ 2. while(...)j++; 3. }
2.容易与双指针滑动窗口扯上关系的最值问题，在双指针前声明返回值res，有时还需要储存每一轮数据的cnt、ans，在数据变动后与res进行比较
#include <iostream> using namespace std; const int N = 1e7; typedef long long ll; int st[N],num[N]; int main(){ int n,k; cin >> n >> k; for(int i = 0;i < n;i++){ cin >> num[i]; } for(int i = 0;i < n;i++){ cin >> st[i]; } int res = 0; for(int i = 0;i < n;i++){ if(st[i] == true) res += num[i]; } // cout << "res = " << res; int sum = 0,maxn = 0; for(int i = 0,j = 0;i < n;i++){ if(st[i] == false) sum += num[i]; // cout << "sum = " << sum <<" "; if(i - j + 1 > k){ if(st[j] == false) sum -= num[j]; j++; } // cout << "sum = " << sum <<" "; maxn = max(sum,maxn); // cout << "maxn = " << maxn << " "; } cout << maxn + res; return 0; }
********************************
题解代码
或者是用i-k来代替慢指针
只需操控一个指针，比较方便
此题是i > k + 1 后，j始终会随着i移动，且差值始终为k，所以根本不需要双指针
双指针是i，j会根据情况来改变移动情况时用的
#include<iostream> using namespace std; const int N = 1e6; int main(){ bool st[N]; int a[N]; int n,k; scanf("%d%d",&n,&k); for(int i = 1;i <= n;i++){ cin >> a[i]; } for(int i = 1;i <= n;i++){ scanf("%d",&st[i]); } int res= 0,maxn = 0,sum = 0; for(int i = 1;i <= n;i++){ if(st[i] == true) sum+=a[i]; else maxn += a[i]; if(i >= k + 1){ if(st[i-k] == false) { maxn -= a[i-k]; } } res = max(maxn,res); } printf("%d",res+sum); return 0; }
