自动搬运

查看原文

来自洛谷，原作者为

	No_Rest I'll journey with you till the end

搬运于2025-08-24 22:53:32，当前版本为作者最后更新于2023-12-24 18:19:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

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

通过思考可以发现，连续 $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;
}