It's the second question of the intramural contest!
To celebrate successfully reaching the second question, you want to express your joy as much as possible using the digit 2, like 222….; where you have a maximum of K chances to change any digit to your desired value.
Given N numbers, under the condition that you can change at most K numbers, how many "consecutive 2s" can you find at most?
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains two integers N and K, representing the total number of digits and the number of changes allowed, respectively.
1 ≤ N ≤ 8*10^4 0 ≤ K ≤ N The second line consists of N integers from left to right, denoted as x_i, representing the digit content. 0 ≤ x_i ≤ 2 | The maximum length of "consecutive 2s" that can be found under the condition that at most K numbers can be changed. |
| 14 2 2 2 0 2 0 0 0 2 2 2 0 0 2 2 | 7 |
| 6 2 2 2 0 2 2 0 | 6 |
Thought Process
Set three variables l = 0, zero = 0, ans = -99999. Run a For loop for (int r = 0; r<N; r++), where l represents the left boundary and r represents the right boundary. When the number at position r is not 2, increment zero, and check if zero is greater than K. If it is, run a While loop to find where the previous non-2 number is, and if the number at position l is 2, increment l, otherwise break out of the While loop and increment l again outside the While loop. Each time, regardless of whether it is 2 or not, check if r - l + 1 is the maximum value.
Sample Code－ZeroJudge K571: The Second Problem
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, K;
cin >> N >> K;
vector<int>num;
for (int i = 0; i<N; i++) {
int tmp;
cin >> tmp;
num.push_back(tmp);
}
int l = 0, zero = 0, ans = -99999;
for (int r = 0; r<N; r++) {
if (num[r] != 2) {
zero++;
if (zero > K) {
while(true) {
if(num[l] == 2) l++;
else break;
}
l++;
}
}
ans = max(ans, r-l+1);
}
cout << ans << "\n";
}
//ZeroJudge K571
//Dr. SeanXD