{"problem":{"name":"[USACO23DEC] Cowntact Tracing 2 B","description":{"content":"Farmer John 有 $N$ 头奶牛排成一列（$1 \\leq N \\leq 3\\cdot 10^5$）。不幸的是，有一种疾病正在传播。 最初，有一些奶牛被感染。每到夜晚，被感染的奶牛会将疾病传播给它左右两边的奶牛（如果这些奶牛存在的话）。一旦奶牛被感染，她就会持续处于感染状态。 经过一些晚上，Farmer John 意识到情况已经失控，因此他对奶牛进行了检测以确定哪些奶牛感染了疾病。请找","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9975"},"statements":[{"statement_type":"Markdown","content":"Farmer John 有 $N$ 头奶牛排成一列（$1 \\leq N \\leq 3\\cdot 10^5$）。不幸的是，有一种疾病正在传播。\n\n最初，有一些奶牛被感染。每到夜晚，被感染的奶牛会将疾病传播给它左右两边的奶牛（如果这些奶牛存在的话）。一旦奶牛被感染，她就会持续处于感染状态。\n\n经过一些晚上，Farmer John 意识到情况已经失控，因此他对奶牛进行了检测以确定哪些奶牛感染了疾病。请找出最少有多少头奶牛最初可能感染了这种疾病。\n\n## Input\n\n第一行为一个整数 $N$，即 Farmer John 拥有的奶牛数量。\n\n接下来一行，包含长度为 $N$ 的由 $1$ 和 $0$ 组成的位串。其中 $1$ 表示一头被感染的奶牛，$0$ 表示一头在经过若干晚之后仍未被感染的奶牛。\n\n## Output\n\n输出一个整数，表示最少有多少头奶牛可能最初感染了这种疾病。\n\n[samples]\n\n## Note\n\n### 样例解释 1\n\n假设只有中间的奶牛最初被感染。那么，奶牛们将按以下顺序被感染：\n\n- 第 $0$ 晚：$00100$（第三只奶牛一开始被感染）\n- 第 $1$ 晚：$01110$（第二和第四只奶牛现在被感染了）\n- 第 $2$ 晚：$11111$（第一和第五只奶牛现在被感染了）\n- 第 $3$ 晚：$11111$（所有的奶牛都已经被感染了，没有新的奶牛被感染）\n- ……\n\n经过两个或更多的晚上，奶牛们的状态即与输入的状态相符。还有许多其他的初始状态和夜晚数量可能导致了输入的状态，例如：\n\n- 第 $0$ 晚：$10001$\n- 第 $1$ 晚：$11011$\n- 第 $2$ 晚：$11111$\n\n或者：\n\n- 第 $0$ 晚：$01001$\n- 第 $1$ 晚：$11111$\n\n或者：\n\n- 第 $0$ 晚：$01000$\n- 第 $1$ 晚：$11100$\n- 第 $2$ 晚：$11110$\n- 第 $3$ 晚：$11111$\n\n所有这些初始状态中至少有一头奶牛被感染。\n\n### 样例解释 2\n\n唯一可能导致这个最终状态的初始状态和夜晚数是：没有经过任何夜晚，输入中的四头感染的奶牛都是从最开始就感染了这种疾病。\n\n### 测试点性质\n\n- 测试点 $3-7$ 满足 $N \\le 1000$。\n- 测试点 $8-12$ 没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9975","tags":["贪心","二分","USACO","2023","O2优化"],"sample_group":[["5\n11111","1"],["6\n011101","4"]],"created_at":"2026-03-03 11:09:25"}}