ZeroJudge K571: 關於第二道題這件事

「好耶！是校內賽第二題！」

為了慶祝順利寫到第二題，你想要用盡可能多的 2，也就是 222…. 來表達你的喜悅之情；
其中你有最多 K 次機會，能夠把任意位置的數字改變成你想要的值。

給定 N 個數字，
在最多只能改變其中 K 個數字的情況下，最多可以找到幾個「連續的 2」呢？

範例測資

範例輸入範例輸出
第一行有兩個整數 N 和 K，代表數字總數 和 可改變次數
1 ≤ N ≤ 8*104
0 ≤ K ≤ N
第二行由左至右有 N 個整數 xi，代表數字內容
0 ≤ xi ≤ 2		至多只能改變 K 個數字的情況下
最多可以找到的「連續的 2」的長度
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

解題思路

預設三個變數 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 是否為最大值。

範例程式碼－ZeroJudge K571: 關於第二道題這件事

#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
標籤

相關文章

發佈留言