爱辉网站建设,哪里有网站建设多少钱,商标查询小程序,网站建设硬件设备密接牛追踪2
农夫约翰有 N 头奶牛排成一排#xff0c;从左到右依次编号为 1∼N。
不幸的是#xff0c;有一种传染病正在蔓延。
最开始时#xff0c;只有一部分奶牛受到感染。
每经过一个晚上#xff0c;受感染的牛就会将病毒传染给它左右两侧的牛#xff08;如果有的话…密接牛追踪2
农夫约翰有 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)#includebits/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 pairint,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::vectorpii 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();
}
