USACO历年青铜组真题解析 | 2023年12月Cowntact Tracing 2

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考青铜组别比赛学习过程中的题目，记录每一个瞬间。

附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客

【题目描述】

农夫约翰(FJ)的N头(1≤N≤3?10^5)奶牛排成一行。不幸的是，疾病正在这些奶牛中传播。

有些奶牛初始就已经被感染了。每天晚上，都会有一头被感染的奶牛把疾病传播给它左右两边的奶牛（如果它们存在的话）。一旦一头奶牛被感染，她就会持续处于感染状态。

在经过了一段时间后，农夫约翰意识到问题已经无法控制了, 所以他对他的奶牛进行检测来确定哪些奶牛感染了这种疾病。找出最初感染这种疾病的奶牛数量的最小值。

【输入】

第一行包含一个整数N，表示农夫约翰拥有的奶牛数量。

第二行包含一个长度为N的字符串，这个字符串只包含1和0，用来表示若干个晚上后每头奶牛的感染状态，其中1表示被感染了，0表示没有被感染。

【输出】

输出一个整数：最初感染这种疾病的奶牛数量的最小值。

【输入样例】

5
11111

【输出样例】

1

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, minl=1e9, maxl=-1e9, minr=1e9, maxr=-1e9, minn=1e9, minm=1e9, left1=0, right1=0, sum=0;
int cnt0=0, cnt1=0;
int a[300005];
string s;
int main()
{
    cin >> n >> s;  // 输入n和0、1字符串
    s = " " + s + " ";  // 字符串的2端增加空格
    for (int i=1; i<=n; i++) {  // 统计1的个数
        if (s[i]=='1') cnt1++;
        else cnt0++;
    }
    if (cnt1==n) {  // 如果全为1，则输出1
        cout << 1 << endl;
        exit(0);
    }
    if (cnt0==n) {  // 如果全为0，则输出0
        cout << 0 << endl;
        exit(0);
    }
    if ((s.find("010")>=0 && s.find("010")<=n) || (s.find(" 10")>=0 && s.find(" 10")<=n) || (s.find("01 ")>=0 && s.find("01 ")<=n) || (s.find("0110")>=0 && s.find("0110")<=n)) {  // 进行特判，该些场景下最初1的个数就是现在1的个数
        cout << cnt1 << endl;
        exit(0);
    }
    int st=1, ed=n;  // 定义起始和结束位置
    if (s[1]=='1') {  // 从起始位置开始，找左端连续1的个数
        for (int i=1; i<=n; i++) {
            if (s[i]=='0') {
                st = i;
                break;
            }
            left1++;
        }
    }
    if (left1>0) {  // 如果有的话，left1可调整的最小值为left1-1（其实就是最大值）
        minn = min(minn, left1-1);
    }
    if (s[n]=='1') {  // 从结束位置开始，找右端连续1的个数
        for (int i=n; i>=1; i--) {
            if (s[i]=='0') {
                ed = i;
                break;
            }
            right1++;
        }
    }
    if (right1>0) {  // 如果有的话，right1可调整的最小值为right1-1（其实就是最大值）
        minn = min(minn, right1-1);
    }
    int tmp = 0, group=0;  // 定义中间连续1个个数tmp和有多少组group
    char last = s[st];  // 此时st位置为从左边的第一个0
    for (int i=st+1; i<=ed; i++) {  // 从左边的第一个0开始
        if (s[i]=='1') {  // 如果是1
            tmp++;  // 个数自增1
        } else if (last=='1' && s[i]!='1'){  // 如果遇到1之后的第一个0
            a[group] = tmp;  // 记录该连续1的个数，并存到数组中
            tmp=0;  // 重置tmp为0
            group++;  // 组数自增1
        }
        last = s[i];  // 更新last为当前字符
    }
    for (int i=0; i<group; i++) {  // 统计中间连续1中最小调整次数
        if (a[i]%2==1) {  // 分奇偶讨论
            minn = min(minn, (a[i]-1)/2);
        } else {
            minn = min(minn, (a[i]-2)/2);
        }
    }
    for (int i=0; i<group; i++) {  // 得到最小调整次数后，计算中间每段连续1的初始1的个数，并累积求和
        sum += (a[i]+(2*minn+1-1))/(2*minn+1);
    }
    if (left1>0) {  // 计算左端连续1的初始1个数 
        int tmp = (left1+2*minn)/(2*minn+1);
        if (tmp>=left1) {  // 当根据公式计算的值大于等于left1个数时
            sum += left1-minn;  // 就加上left1-minn，即开始最左边为1
        } else {  // 否则像计算中间一样计算并累加
            sum += tmp;
        }
    }
    if (right1>0) {  // 计算右端连续1的初始1个数 
        int tmp = (right1+2*minn)/(2*minn+1);
        if (tmp>=right1) {  // 当根据公式计算的值大于等于right1个数时
            sum += right1-minn;  // 就加上right1-minn，即开始最右边为1
        } else {  // 否则像计算中间一样计算并累加
            sum += tmp;
        }
    }
    cout << sum << endl;  // 输出结果
    return 0;
}

【运行结果】

5
11111
1