[USACO23DEC] Cowntact Tracing 2 B

· · 题解

[USACO23DEC] Cowntact Tracing 2 B

题意简述

一个农场，农场里有 N 头奶牛排成一列。有一种疾病正在传播，最初，有一些奶牛被感染。每到夜晚，被感染的奶牛会将疾病传播给它左右两边的奶牛（如果这些奶牛存在的话）。一旦奶牛被感染，她就会持续处于感染状态。经过一些晚上，农场主人意识到情况已经失控，因此他对奶牛进行了检测以确定哪些奶牛感染了疾病。题目要求找出最少有多少头奶牛最初可能感染了这种疾病。

思路分析

省流：通过模拟疾病的传播过程，来找出最少有多少头奶牛最初可能感染了这种疾病。

首先，读入奶牛的数量 N 和每头奶牛的状态。状态被存储在数组中，其中 1 表示奶牛被感染，0 表示奶牛未被感染。

然后，遍历了所有的奶牛。如果一头奶牛被感染，检查前一头奶牛的状态。如果前一头奶牛未被感染，增加一段连续感染，并初始化该段的感染奶牛数量为 1。如果前一头奶牛被感染，增加当前段的感染奶牛数量。这一步的目的是找出所有连续感染的段，并记录每一段的感染奶牛数量。

接下来，计算了中间段的最小感染天数。这是通过对每一段连续感染的奶牛数量减一后除以二得到的。这一步的目的是找出最小的感染天数，因为这个值决定了最初可能感染的奶牛数量。

注意检查第一头奶牛和最后一头奶牛的状态，如果她们被感染，代码会更新最小感染天数。这一步的目的是确保最小感染天数的计算考虑到了所有可能的情况。

最后，代码计算了最少感染奶牛数量。具体方法见代码第 23 行。

复杂度分析

时间复杂度分析

设连续感染的段数为 K，显然时间复杂度为 O(K+N).因为 K \le \frac{1}{2}N，所以时间复杂度去掉常数为 O(N)。

空间复杂度分析

显然，O(N)。

数据范围

数据范围：1 \le N \le 3 \cdot 10^5.

最劣时间：N=3 \cdot 10^5 \le 10^8，显然不会超时。

空间：N=3 \cdot 10^5 \le 3 \cdot 10^7\space_{[1]}，显然不会超空间。

代码实现

#include <bits/stdc++.h>//导入所有标准库
using namespace std;//使用标准命名空间
typedef long long ll;//定义长整型别名为ll
ll n,a[300005],my_array[300005],my_len = 0,minn = 2147483647,ans = 0;//定义全局变量，n为奶牛数量，a[i]为第i头奶牛的状态，my_array[i]为第i段连续感染的奶牛数量，my_len为连续感染的段数，minn为最小感染天数，ans为最少感染奶牛数量
char ch;//定义字符变量，用于读入奶牛的状态
int main(){//主函数开始
    scanf("%lld",&n);//读入奶牛数量
    for(ll i = 1;i <= n;i++){//对于每头奶牛，进行以下操作
        scanf(" %c",&ch);//读入奶牛的状态
        a[i] = ch - '0';//将字符转换为数字
    }
    for(ll i = 1;i <= n;i++){//对于每头奶牛，进行以下操作
        if(a[i] == 1){//如果奶牛被感染
            if(a[i - 1] == 0)my_array[++my_len] = 1;//如果前一头奶牛未被感染，增加一段连续感染，初始化该段的感染奶牛数量为1
            if(a[i - 1] == 1)my_array[my_len]++;//如果前一头奶牛被感染，增加当前段的感染奶牛数量
        }
    }
    for(ll i = 2;i <= my_len - 1;i++)if((my_array[i] - 1) / 2 < minn)minn = (my_array[i] - 1) / 2;//计算中间段的最小感染天数
    if(a[1] == 1)minn = min(minn,my_array[1] - 1);//如果第一头奶牛被感染，更新最小感染天数
    else minn = min(minn,(my_array[1] - 1) / 2);//如果第一头奶牛未被感染，更新最小感染天数
    if(a[n] == 1)minn = min(minn,my_array[my_len] - 1);//如果最后一头奶牛被感染，更新最小感染天数
    else minn = min(minn,(my_array[my_len] - 1) / 2);//如果最后一头奶牛未被感染，更新最小感染天数
    for(ll i = 1;i <= my_len;i++)ans += (my_array[i] + 2 * minn) / (2 * minn + 1);//计算最少感染奶牛数量
    printf("%lld",ans);//输出最少感染奶牛数量
    return 0;//主函数返回0，表示程序正常结束
}

注：

[1]：经计算，若所有变量均为长长整型，最多可以使用约 3 \cdot 10^7 个变量。