Farmer John's Sickness Problem

问题描述

Farmer John 有 N 头奶牛排成一排（1 ≤ N ≤ 3·10^5）。不幸的是，有一种疾病正在传播。

最初，有些奶牛开始被感染。每晚，被感染的奶牛会将其疾病传播给左边和右边的奶牛（如果它们存在）。一旦奶牛被感染，她就会一直保持感染状态。

经过一定数量的夜晚后，Farmer John 意识到问题已经失控，所以他测试了他的奶牛来确定哪些奶牛已经被感染。请找出最初可能被感染的奶牛的最小数量。

输入格式（从终端/标准输入读入）

• 第一行包含一个整数 N，表示 Farmer John 的奶牛数量。
• 第二行包含一个长度为 N 的由 1 和 0 组成的字符串，其中 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

样例解释

唯一可能导致这种最终状态的初始状态和夜晚数量是如果没有经过任何夜晚，输入中的四头被感染的奶牛一开始就处于被感染状态。

评分标准

• 测试点 3-7: N ≤ 1000
• 测试点 8-12: 没有额外约束
• 问题提供者: Suhas Nagar

一本通在线评测