كيف يمكنني حل هذه المشكلة لجميع القيود

لدى المزارع جون عدد N من الأبقار في خط (1≥N≥3⋅10^5). لسوء الحظ، هناك مرض منتشر في كل مكان.
في البداية، تبدأ بعض الأبقار بالعدوى. في كل ليلة، تنشر بقرة مصابة المرض إلى الأبقار التي على يسارها ويمينها (إن وجدت). بمجرد إصابة البقرة بالعدوى، فإنها تظل مصابة.
بعد مرور بعض الوقت، يدرك المزارع جون أن المشكلة قد خرجت عن نطاق السيطرة، لذلك يقوم باختبار أبقاره لتحديد من هو المصاب بالمرض. أوجد أقل عدد ممكن من الأبقار التي يمكن أن تكون قد بدأت بالمرض.
مدخل:
يحتوي السطر الأول على N، وهو عدد الأبقار التي يملكها المزارع جون.
يحتوي السطر التالي على سلسلة بت من الأحرف N مكونة من 1 و0 فقط حيث يمثل 1 بقرة مصابة ويمثل 0 بقرة غير مصابة بعد عدد من الليالي.
انتاج:
إخراج عدد صحيح واحد: الحد الأدنى لعدد الأبقار التي يمكن أن تكون قد بدأت بالمرض.
إدخال العينة:
5
11111

إخراج العينة:
1

لنفترض أن البقرة الوسطى هي البقرة الوحيدة التي أصيبت بالعدوى. ثم تصاب الأبقار بالترتيب التالي:
0 ليلة: 00100 (البقرة الثالثة تصاب في البداية)
ليلة واحدة: -> 01110 (البقرتان الثانية والرابعة مصابتان الآن)
ليلتان: -> 11111 (البقرة الأولى والخامسة مصابتان الآن)
3 ليال: -> 11111 (جميع الأبقار مصابة بالفعل، لذا لا توجد أبقار أخرى مصابة)
-> …

وبعد ليلتين أو أكثر، ستبدو الحالة النهائية للأبقار مثل المدخلات. هناك العديد من الحالات الأولية الأخرى وعدد الليالي التي كان من الممكن أن تنتج حالة الإدخال، مثل:
0 ليال: 10001
ليلة واحدة: -> 11011
ليلتين: -> 11111

أو:
0 ليالي: 01001
ليلة واحدة: -> 11111

أو:
0 ليالي: 01000
ليلة واحدة: -> 11100
ليلتين: -> 11110
3 ليالي: -> 11111

تحتوي كل هذه الحالات الأولية على بقرة واحدة مصابة على الأقل.
إدخال العينة:
6
011101

إخراج العينة:
4

ما حاولت:

لقد جربت حلين مختلفين، واجتازت بعض نقاط الاختبار، بعضها مختلف:
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;
}


This is my basic logic, however I do believe it may be incorrect.

Logic for counting how many cows (n is a constant for a number of 1s):

Middle cases:
If there is a sequence of 1s with only a single 1 (a sequence is a continued string of 1s, separated by 0s from other 1s), count how many 1s there are to find total.
If there is a sequence of 2 1s, count how many 1s there are to find total
If there is a sequence of n 1s, where n is odd and n>=3, use the formula: x=(n+1)/2 to determine the day it is. Then apply the formula n=2x-1 to weed through all sequences of consecutive 1s to determine if the day count is correct.
If it is not correct (a sequence of an even number of consecutive 1s) or (an odd number of 1s not equating to the aforementioned string), count how many 1s there are to find total.
If it is correct and applies to all other sequences, add 1 to the total.

Special cases (on both ends):
If the bitstring starts with 10, erase current total and count how many 1s there are to find correct total.
If the bitstring ends in 01, erase current total and count how many 1s there are to find correct total.
If the bristring starts with 110, there may be 2 original cows, or only 1, depending on the middle sections.
If the bristring ends with 011, there may be 2 original cows, or only 1, depending on the middle sections.
If the bitstring starts with x0 (where z is a bitstring representing the number x of 1s), there may be x original cows or only 1, depending on the middle sections.
If the bitstring starts with 0x (where z is a bitstring representing the number x of 1s), there may be x original cows or only 1, depending on the middle sections.