P9975 [USACO23DEC] Cowntact Tracing 2 B 题解

· · 题解

思路

为了让最开始感染的牛尽量少，我们要让传染的天数尽量多。我们可以先求出这个天数，再根据天数来倒推最开始最少的感染牛数。

通过思考可以发现，连续 x 只感染的牛最多通过 \lfloor \frac{x-1}{2} \rfloor 天的传染得到（想象一只牛在中间，每天都把两边的牛传染到）。通过样例二可以发现，整群牛最多传染天数是所有连续的牛的最多传染天数中的最少天数。

让我们假设这个求出来的天数是 m。确定天数后，我们就可以倒推牛数了。每只牛在 m 天后会传染左面、右面各 m 只牛，算上自己，会传染 2m+1 只牛。因此，为了最初感染的牛最少，我们每 2m+1 只牛就只把中间的那头牛当最初感染的牛。这样的话，连续 x 只感染的牛中，最少会有 \lceil \frac{x}{2m+1} \rceil 只是最初感染的。

最后是要注意边界，因为边界的情况与中间不太一样。在边界，连续 x 只牛能传染 x - 1 天。

代码

#include<iostream>
#include<vector>
#include<cmath>
#define ll long long
#define in inline
#define re register
using namespace std;
const ll maxn = 3e5 + 5;
in ll read(){
    char ch;
    ll f = 1, r = 0;
    ch = getchar();
    while(ch > '9' || ch < '0'){ if(ch == '-') f = -1; ch = getchar();}
    while(ch <= '9' && ch >= '0') r = (r << 3) + (r << 1) + (ch ^ 48), ch = getchar();
    return r * f;
}
in void write(ll f){
    if(f < 0) f = -f, putchar('-');
    if(f > 9) write(f / 10);
    putchar(f % 10 + '0');
    return;
}
ll n = read(), a[maxn], ans[maxn], mn = maxn, last, cnt;
vector <ll> st, ed;//记录每一段连续感染奶牛的起点和终点
int main(){
    for(re ll i = 1; i <= n; ++i){
        scanf("%1d", &a[i]);
        if(a[i]){
            last++;
            if(!a[i - 1]) st.push_back(i);//一段连续感染奶牛的开始
        } else if(!a[i] && last){
            if(st[st.size() - 1] == 1) mn = min(mn, i - 2);//注意边界
            else mn = min(mn, (last - 1) / 2);//计算最多天数
            last = 0, ed.push_back(i - 1);
        }
    }
    if(last) mn = min(mn, last - 1), ed.push_back(n);//最后别忘了
    for(re ll i = 0; i < st.size(); ++i) cnt += ceil(1.0 * (ed[i] - st[i] + 1) / (2 * mn + 1));//计算牛数
    write(cnt);
    return 0;
}