ZeroJudge K571: The Second Problem

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

預設三個變數 l = 0、zero = 0、ans = -99999。跑一個 For迴圈 for (int r = 0; r<N; r++)，l 代表左邊界，r 代表右邊界。當 r 位置不是 2 時，將 zero++，並且判斷 zero 是否有 > K，如果有的話，就要跑一個 While 迴圈，尋找上一個 非 2 數字的下一個 2 在哪裡，如果 l 位置的數字是 2 ，則 l++，否則就將 While迴圈 break，並且在 While迴圈外面再進行一次 l++。每一次不管是不是 2 都需要判斷 r – l +1 是否為最大值。

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
Tags

Related Posts

Comments