2018年做网站还能,深圳网站建设加q479185700,网站添加支付功能,网站设计风格怎么写题意就是 在这个数串中插入1构成一个最长的连续1的区间串 如何做#xff1f;我们可以对长度进行二分
从1到n二分长度 然后在对这个长度拿到数串中查看是否能构成最终我们想要的最长匹配串
这里我们可以利用一个前缀和数组 统计从1到i的0的个数 由于必然是递增数组 就满足了二…
题意就是 在这个数串中插入1构成一个最长的连续1的区间串 如何做我们可以对长度进行二分
从1到n二分长度 然后在对这个长度拿到数串中查看是否能构成最终我们想要的最长匹配串
这里我们可以利用一个前缀和数组 统计从1到i的0的个数 由于必然是递增数组 就满足了二分
的“有序”条件 。 #includebits/stdc.h
using namespace std;
int a[300010],s[300010];
int n,k,L;
bool che(int x)
{for(int i1;in;i){int r ix-1;if(rn)return 0;if(s[r]-s[i-1]k){//如果s[r]-s[i-1]k说明这两个下标下之间0的个数k也就说满足条件 就会返回1 并记录区间左端点L i;return 1;}}return 0;
}
int main()
{cinnk;s[0]0; for(int i1;in;i){ cina[i];s[i]s[i-1](a[i]0);}int M0,u0;int l 1,rn;while(lr){int mid (lr)1;if(che(mid)){// 如果这里返回1 说明区间满足条件 就会记录长度 尝试更长的长度 u mid;l mid1;}else r mid-1;// 不满足条件 说明数串长度过长 需要截短}for(int iL;iLu-1;i)a[i]1;coutuendl;for(int i1;in;i){couta[i];if(in)puts();else cout ;}return 0;}
