二分小结

二分概述

二分不同于分治,它根据问题的单调维度求解的特点,在该维度上折半查找答案,使复杂度系数由 降低到 .

[TJOI2007] 路标设置

求最大距离的最小值,典型的二分答案

#include<bits/stdc++.h>
using namespace std;
int l,n,k,L=0,R=0;
int a[100005];
bool check(int p){
    int t=0;
    for(int i=1;i<n;i++)t+=a[i]/p-(a[i]%p?0:1);
    return t<=k;}
int main(){scanf("%d%d%d",&l,&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<n;i++)a[i]=a[i+1]-a[i],R=max(R,a[i]);
    while(L<R){int mid=(L+R)>>1;
        if(check(mid))R=mid;
        else L=mid+1;
    }
    printf("%d",L);
    return 0;
}

[POJ2018]Best Cow Fences

二分平均值,每个数减掉平均值

然后处理前缀和,问题转化为是否存在 满足 .

一个变量维护最优决策 j 即可.

总复杂度 .

#include<cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=100005;
int n,l,mxa;
int a[N];

bool check(double k){double t[N],pre=0;
    t[0]=0;
    for(int i=1;i<=n;i++)t[i]=t[i-1]+a[i]-k;
    for(int i=l;i<=n;i++){pre=min(pre,t[i-l]);
        if(t[i]-pre>0)return 1;
    }
    return 0;
}

int main(){scanf("%d%d",&n,&l);
    for(int i=1;i<=n;i++){scanf("%d",&a[i]);
        mxa=max(mxa,a[i]);
    }
    double l=0,r=mxa;
    while(r-l>1e-6){double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%d",(int)(r*1000));
    return 0;
}

[NOIP2012] 借教室

二分答案,前缀和验证即可

#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000006,M=1000006;
int n,m;
int a[N],d[M],s[M],t[M];
long long pre[N];
bool check(int k){memset(pre,0,sizeof(pre));
    for(int i=1;i<=k;i++)pre[s[i]]+=d[i],pre[t[i]+1]-=d[i];
    for(int i=1;i<=n;i++){pre[i]+=pre[i-1];
        if(pre[i]>a[i])return false;
    }
    return true;
}
int main(){scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&d[i],&s[i],&t[i]);
    int l=1,r=m;
    while(l<r){int mid=(l+r)>>1;
        if(check(mid))l=mid+1;
        else r=mid;
    }
    if(l==m&&check(m))puts("0");
    else printf("-1\n%d",l);
    return 0;
}

  转载请注明: Sshwy's Blog 二分小结

 上一篇
[LuoguP3386] 二分图匹配 [LuoguP3386] 二分图匹配
分析网络流算法,左部右部分别连源点汇点,置容量为 1,跑一遍 dinic 或者 EK 即可 代码#include<cstdio> #include<cstring> #include<queue> using namesp
2018.12.21
下一篇 
搜索小结 搜索小结
搜索概述搜索问题的解,其实就是在问题对应的状态空间中进行映射与遍历. 使用递归,循环,数据结构等对状态空间的单调性,对称性,有解性进行排列归纳,加以搜索,以快速找到问题的答案 LuoguP1120 小木棍DFS 剪枝,在洛谷的毒瘤时间范围下
2018.12.19
  目录