时间限制：2秒
空间限制：131072K
给你一个01字符串，定义答案=该串中最长的连续1的长度，现在你有至多K次机会，每次机会可以将串中的某个0改成1，现在问最大的可能答案
输入描述:
输入第一行两个整数N,K，表示字符串长度和机会次数 第二行输入N个整数，表示该字符串的元素 ( 1 <= N <= 300000 , 0 <= K <= N )输出描述:
输出一行表示答案输入例子1:
10 2 1 0 0 1 0 1 0 1 0 1输出例子1:
5
这道题目有一定难度，思路是将所有0的位置存下来，然后用滑窗的方法解决。
#include <iostream> #include <vector> using namespace std; const int N = 300010; int arr[N]; int main() { int n,k; vector<int> res; cin>>n>>k; for(int i=0;i<n;i++){ cin>>arr[i]; if(arr[i]==0) res.push_back(i); } // 0的个数小于k if(res.size()<=k){ cout<<n<<endl; return 0; } // 全是0 if(res.size()==n){ cout<<k<<endl; return 0; } int maxlen = 0; /*if(k==0){ int count = 0; for(int i=0;i<n;i++){ if(arr[i]==1) count++; else count=0; maxlen=max(maxlen,count); } cout<<maxlen<<endl; return 0; }*/ for(int i=0;i<res.size()-k;i++){ if(i==0){ maxlen = res[i+k]; } else{ maxlen =max(maxlen,res[i+k]-res[i-1]-1); cout<<maxlen<<endl; } } cout<<maxlen<<endl; system("pause"); return 0; }
