【蓝桥杯集训·每日一题2025】 AcWing 5438. 密接牛追踪2 python

5438. 密接牛追踪2

Week 2
2月26日

题目描述

农夫约翰有 $N$ 头奶牛排成一排，从左到右依次编号为 $\sim N$ 。

不幸的是，有一种传染病正在蔓延。

最开始时，只有一部分奶牛受到感染。

每经过一个晚上，受感染的牛就会将病毒传染给它左右两侧的牛（如果有的话）。

一旦奶牛被感染，它就会一直被感染，无法自愈。

给定一个经过若干个夜晚后的奶牛的整体状态，其中哪些奶牛已经被感染，哪些奶牛尚未被感染统统已知。

请你计算，最开始时就受到感染的奶牛的最小可能数量。

输入格式

第一行包含整数 $N$ 。

第二行包含一个长度为 $N$ 的 $01$ 序列，用来表示给定的奶牛的整体状态，其中第 $i$ 个字符如果是 $1$ 则表示第 $i$ 头奶牛已经被感染，如果是 $0$ 则表示第 $i$ 头奶牛尚未被感染。

输出格式

一个整数，表示最开始时就受到感染的奶牛的最小可能数量。

数据范围

$\le N \le 3 \times 10^5$

输入样例1：

5
11111

输出样例1：

样例1解释

初始时，任意一头奶牛被感染，一定天数后都可以使得所有奶牛被感染。

输入样例2：

6
011101

输出样例2：

样例2解释

唯一一种可能是给定状态是没有经过任何夜晚时所有奶牛的状态，所以输入中被感染的 $4$ 头奶牛都在最开始时就受到感染。

实现code

python">import mathn = int(input())
s = input()
a = []
day = float('inf')
i = 0
while i < n:if s[i] == '0':i += 1continueelse:j = i + 1while j < n and s[j] == '1':j += 1len = j - ia.append(len)res = (len - 1) // 2if i == 0 or j == n:res = len - 1day = min(res, day)i = jans = 0
for i in a:ans += math.ceil(i / (2 * day + 1))
print(ans)

要解决这个问题，我们需要找到一种方法来确定在最开始时被感染的奶牛的最小数量。我们可以通过分析给定的01序列来推断出最初被感染的奶牛的位置。

问题分析

感染传播规则：每经过一个晚上，受感染的奶牛会将其左右两侧的奶牛感染（如果有的话）。
目标：给定一个经过若干夜晚后的感染状态，找到最初被感染的奶牛的最小数量。

解题思路

分段处理：将连续的1（被感染的奶牛）分成若干段，每一段代表一个连续的感染区域。
计算最小初始感染数：对于每一段连续的1，计算在最开始时需要有多少头奶牛被感染才能达到当前的感染状态。
合并结果：将所有段的初始感染数相加，得到最终的最小初始感染数。

具体步骤

遍历序列：遍历给定的01序列，找到所有连续的1的段。
计算每段的初始感染数：对于每一段连续的1，计算在最开始时需要有多少头奶牛被感染才能达到当前的感染状态。这个可以通过计算每段的长度和传播的天数来确定。
累加结果：将所有段的初始感染数相加，得到最终的最小初始感染数。

python">import mathn = int(input())
s = input()# 存储每一段连续1的长度
a = []
# 初始化最小天数为无穷大
day = float('inf')i = 0
while i < n:if s[i] == '0':i += 1continueelse:j = i + 1while j < n and s[j] == '1':j += 1length = j - ia.append(length)# 计算当前段的最小初始感染数res = (length - 1) // 2if i == 0 or j == n:res = length - 1day = min(res, day)i = j# 计算最终的最小初始感染数
ans = 0
for length in a:ans += math.ceil(length / (2 * day + 1))print(ans)

代码解释

遍历序列：通过while循环遍历序列，找到所有连续的1的段，并记录每段的长度。
计算最小初始感染数：对于每一段连续的1，计算在最开始时需要有多少头奶牛被感染。这个计算基于每段的长度和传播的天数。
累加结果：将所有段的初始感染数相加，得到最终的最小初始感染数。

示例

输入1：
```
5
11111
```
输出1：
```
1
```
解释：任意一头奶牛被感染，经过一定天数后都可以使得所有奶牛被感染。
输入2：
```
6
011101
```
输出2：
```
4
```
解释：唯一一种可能是给定状态是没有经过任何夜晚时所有奶牛的状态，所以输入中被感染的4头奶牛都在最开始时就受到感染。

通过这种方法，我们可以有效地计算出最初被感染的奶牛的最小数量。

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注谢谢