如何解决所有约束条件下的这个问题

农夫约翰有 N 头奶牛排成一排 (1≤N≤3⋅10^5)。 不幸的是，有一种疾病正在蔓延。
最初，一些奶牛开始受到感染。 每天晚上，一头受感染的奶牛都会将疾病传播给左右两侧的奶牛（如果存在的话）。 一旦奶牛被感染，她就会一直被感染。
经过几个夜晚后，农夫约翰意识到问题已经失控，因此他对他的奶牛进行了测试，以确定谁患病了。 找出可能开始患病的奶牛的最少数量。
输入：
第一行包含 N，即 Farmer John 拥有的奶牛数量。
下一行包含仅由 1 和 0 组成的 N 个字符位串，其中 1 表示受感染的牛，0 表示经过若干夜晚后未受感染的牛。
输出：
输出一个整数：可能开始患病的奶牛的最小数量。
样本输入：
5
11111

样本输出：
1

假设中间的牛是唯一一头被感染的牛。 然后奶牛会按以下顺序被感染：
0晚：00100（第三头牛最初被感染）
1晚：->01110（第二头和第四头牛现已感染）
2晚：->11111（第一头和第五头牛现已被感染）
3晚：-​​> 11111（所有奶牛都已被感染，因此没有其他奶牛被感染）
-> …

经过两个或更多晚上后，奶牛的最终状态将类似于输入。 还有许多其他初始状态和可能产生输入状态的夜晚数，例如：
0 晚：10001
1 晚：-> 11011
2 晚：-> 11111

或者：
0 晚：01001
1 晚：-> 11111

或者：
0 晚：01000
1 晚：-> 11100
2 晚：-> 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;
}

这是我的基本逻辑，但我确实认为它可能是不正确的。

计算有多少头牛的逻辑（n是一个常数，表示1的个数）：

中间情况：
如果存在一个只有一个 1 的 1 序列（一个序列是一串连续的 1，与其他 1 之间用 0 分隔），计算有多少个 1 以求总数。
如果有 2 个 1 的序列，计算有多少个 1 求总数
如果存在 n 个 1 的序列，其中 n 为奇数且 n>=3，则使用公式：x=(n+1)/2 来确定它是哪一天。 然后应用公式 n=2x-1 剔除所有连续 1 的序列，以确定天数是否正确。
如果不正确（偶数个连续 1 的序列）或（奇数个 1 不等于上述字符串），则计算有多少个 1 以求总数。
如果它是正确的并且适用于所有其他序列，则在总数中加 1。

特殊情况（两端）：
如果位串以 10 开头，则擦除当前总数并计算有多少个 1 以找到正确的总数。
如果位串以 01 结尾，则擦除当前总数并计算有多少个 1 以找到正确的总数。
如果 bristring 以 110 开头，则可能有 2 头原始牛，或者只有 1 头，具体取决于中间部分。
如果 bristring 以 011 结尾，则可能有 2 头原始牛，或者只有 1 头，具体取决于中间部分。
如果位串以 x0 开头（其中 z 是表示 1 数量 x 的位串），则可能有 x 头原始奶牛，也可能只有 1 头，具体取决于中间部分。
如果位串以 0x 开头（其中 z 是表示 1 的 x 数量的位串），则可能有 x 头原始牛，也可能只有 1 头，具体取决于中间部分。