農夫約翰有 N 頭奶牛排成一排，從左到右依次編號為 1～N。

不幸的是，有一種傳染病正在蔓延。

最開始時，只有一部分奶牛受到感染。

每經過一個晚上，受感染的牛就會將病毒傳染給它左右兩側的牛（如果有的話）。

一旦奶牛被感染，它就會一直被感染，無法自愈。

給定一個經過若干個夜晚后的奶牛的整體狀態，其中哪些奶牛已經被感染，哪些奶牛尚未被感染統統已知。

請你計算，最開始時就受到感染的奶牛的最小可能數量。

輸入格式

第一行包含整數 N。
第二行包含一個長度為 N 的 01序列，用來表示給定的奶牛的整體狀態，其中第 i個字符如果是 1 則表示第 i 頭奶牛已經被感染，如果是 0 則表示第 i 頭奶牛尚未被感染。

輸出格式

一個整數，表示最開始時就受到感染的奶牛的最小可能數量。

輸入樣例

5
11111

輸出樣例

4

題意 : 給定01字符串, 求最開始時, 01串中含1的數量,每天01串中的1都會擴散擴散方式如下:

• 每天 1 會向倆端擴展,知道全部 0 變為 1 為止

解題思路:

將擴散轉換為區間問題, 查找最大天數, 因為每個1 每天的擴展區間為 2r + 1 其中 r 為天數, 可以用一個變量cnt統計出每段去間1的數量, 然后套用公式計算出最大天數, 根據最大天數, 計算該段 1 的連續區間最少的 1 的數量。

AC Code

// Problem: 密接牛追蹤2
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/5441/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
typedef long long ll; // 確保 ll 在使用前被定義
using namespace std;
using i64 = long long;
#define f for(int i = 0; i < n;++i)
#define ff for(int i = 1; i <= n;++i)
#define int long long 
#define pii pair<int,int>
#define In \ll n; \std::cin >> n;\

const int mod = 1e9 + 7, N = 1e7;void solve(){In; std::string s;std::cin >> s;int ans = 0;std::vector<pii> ss;// 遍歷每段區間, 將每段區間記錄for(int i = 0, j = 0; i < n; i = j) {while(s[i] == '0') i++;j = i;while(j < n and s[j] == '1') j++;if(j > i) ss.push_back({i , j - 1});}if(ss.size() == 0) {std::cout << 0 << "\n";return ;}// 計算最小天數int R = 1e9;for(auto &[l , r] : ss) {// 最后和首位要特判if(l == 0 or r == n - 1) R = std::min(r - l + 1, R);else R = min((r - l + 2) / 2, R);}// 最后根據答案計算最小感染牛for(auto &[l, r] : ss) {ans += (r - l) / (2 * R - 1) + 1;}std::cout << ans << "\n";
}signed main(){std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);ll T = 1;//std::cin >> T;for(int i = 1; i <= T; ++i) solve();
}