【解決方法】すべての制約についてこの問題を解決するにはどうすればよいですか

農夫のジョンは N 頭の牛を一列に並べています (1≤N≤3⋅10^5)。 残念ながら、病気が蔓延しています。
最初は、一部の牛が感染し始めます。 感染した牛は毎晩、左右の牛（存在する場合）に病気を広めます。 牛が一度感染すると、感染したままになります。
しばらく夜を過ごした後、農夫のジョンは問題が制御不能になったことに気づき、誰が病気に罹っているかを判断するために牛を検査します。 病気が原因である可能性のある牛の最小数を見つけてください。
入力：
最初の行には、農夫ジョンが飼っている牛の数である N が含まれています。
次の行には、1 と 0 だけからなる N 文字のビット列が含まれており、1 は感染した牛を表し、0 は一定の夜を経た感染していない牛を表します。
出力：
単一の整数、つまり病気が始まった可能性のある牛の最小数を出力します。
入力例:
5
11111

サンプル出力:
1

中央の牛が最初から感染した唯一の牛だったと仮定します。 その後、牛は次の順序で感染します。
0 泊: 00100 (3 頭目の牛が最初に感染)
1夜: -> 01110 (2頭目と4頭目の牛が感染)
2 泊: -> 11111 (最初と 5 頭目の牛が感染しました)
3 泊: -> 11111 (すべての牛がすでに感染しているため、追加の牛が感染することはありません)
-> …

2 晩以上経つと、牛の最終的な状態は入力と同じになります。 入力状態を生成する可能性のある初期状態や夜の数は他にも多数あります。次に例を示します。
0泊：10001
1泊: -> 11011
2泊: -> 11111

または：
0泊：01001
1泊: -> 11111

または：
0泊：01000
1泊: -> 11100
2泊: -> 11110
3泊: -> 11111

これらの初期状態にはすべて、少なくとも 1 頭の感染牛が含まれています。
入力例:
6
011101

サンプル出力:
4

私が試したこと:

私は 2 つの異なる解決策を試し、いくつかのテスト ポイントを通過しましたが、いくつかは異なりました。
1.

#include <iostream>
#include <vector>

int calculate_infected_cows(const std::vector<int>& cow_states) {
    int total_infected = 0;
    int consecutive_ones = 0;

    for (int i = 0; i < cow_states.size(); ++i) {
        if (cow_states[i] == 1) {
            consecutive_ones++;
        } else {
            int current_sequence_length = consecutive_ones;
            consecutive_ones = 0;

            if (current_sequence_length == 1 || current_sequence_length == 2) {
                total_infected += current_sequence_length;
            } else if (current_sequence_length >= 3) {
                if (i + 1 < cow_states.size() && cow_states[i + 1] == 0) {
                    total_infected += (current_sequence_length + 1) / 2; // Adjusted logic
                } else {
                    total_infected += current_sequence_length;
                }
            } else {
                total_infected += current_sequence_length;
            }
        }
    }

    // Consider the last cow
    total_infected += consecutive_ones;

    // If all cows are infected, set total_infected to 1
    if (total_infected == cow_states.size()) {
        total_infected = 1;
    }

    return total_infected;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<int> cow_states(n);
    for (int i = 0; i < n; ++i) {
        char c;
        std::cin >> c;
        cow_states[i] = c - '0';
    }

    int result = calculate_infected_cows(cow_states);
    std::cout << result << std::endl;

    return 0;
}

2.

#include <iostream>
#include <vector>

bool is_consecutive_ones(const std::vector<int>& cow_states, int index) {
    return index >= 2 && cow_states[index - 1] == 1 && cow_states[index - 2] == 1;
}

int calculate_infected_cows(const std::vector<int>& cow_states) {
    int total_infected = 0;
    int consecutive_ones = 0;
    bool override_total = false;

    for (int i = 0; i < cow_states.size(); ++i) {
        if (cow_states[i] == 1) {
            consecutive_ones++;
        } else {
            int current_sequence_length = consecutive_ones;
            consecutive_ones = 0;

            if (current_sequence_length == 1 || current_sequence_length == 2) {
                total_infected += current_sequence_length;
            } else if (current_sequence_length >= 3 && current_sequence_length % 2 == 1) {
                if (i + 1 < cow_states.size() && cow_states[i + 1] == 0) {
                    total_infected++;
                } else if (is_consecutive_ones(cow_states, i)) {
                    total_infected++;
                    override_total = true;
                } else {
                    total_infected += current_sequence_length;
                }
            } else {
                if (current_sequence_length == 3) {
                    if (i - 1 >= 0 && cow_states[i - 1] == 0 && i + 1 < cow_states.size() && cow_states[i + 1] == 0) {
                        total_infected++;
                    } else {
                        total_infected += current_sequence_length;
                    }
                } else {
                    total_infected += current_sequence_length;
                }
            }
        }
    }

    if (override_total) {
        total_infected += consecutive_ones;
    } else {
        total_infected += cow_states.back(); // Consider the last cow
    }

    return total_infected;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<int> cow_states(n);
    for (int i = 0; i < n; ++i) {
        char c;
        std::cin >> c;
        cow_states[i] = c - '0';
    }

    int result = calculate_infected_cows(cow_states);
    std::cout << result << std::endl;

    return 0;
}

これが私の基本的なロジックですが、間違っている可能性もあると思います。

牛の数を数えるロジック (n は 1 の数を表す定数):

中間のケース:
1 が 1 つだけ含まれる 1 のシーケンスがある場合 (シーケンスとは、他の 1 から 0 で区切られた 1 の連続した文字列です)、1 が何個あるかを数えて合計を求めます。
1 が 2 つ連続する場合、1 が何個あるか数えて合計を求めます。
n 個の 1 が連続する場合 (n は奇数、n>=3)、式 x=(n+1)/2 を使用して、その日が何日であるかを決定します。 次に、式 n=2x-1 を適用して、連続する 1 のシーケンスをすべて調べて、日数カウントが正しいかどうかを判断します。
正しくない場合 (偶数個の 1 が連続する場合)、または (奇数個の 1 が前述の文字列と一致しない場合)、合計を見つけるために 1 が何個あるかを数えます。
それが正しく、他のすべてのシーケンスに当てはまる場合は、合計に 1 を加えます。

特殊なケース (両端):
ビット文字列が 10 で始まる場合は、現在の合計を消去し、正しい合計を見つけるために 1 が何個あるかを数えます。
ビット文字列が 01 で終わる場合は、現在の合計を消去し、正しい合計を見つけるために 1 が何個あるかを数えます。
牛毛が 110 で始まる場合、中間セクションに応じて、元の牛が 2 頭存在する場合もあれば、1 頭だけ存在する場合もあります。
牛毛が 011 で終わる場合、中間セクションに応じて、元の牛が 2 頭存在する場合もあれば、1 頭だけ存在する場合もあります。
ビット列が x0 で始まる場合 (z は 1 の数 x を表すビット列)、中間セクションに応じて、元の牛が x 頭存在するか、または 1 頭だけ存在する可能性があります。
ビット文字列が 0x で始まる場合 (z は 1 の数 x を表すビット文字列)、中間セクションに応じて、元の牛が x 頭存在するか、または 1 頭だけ存在する可能性があります。