洛谷题单 Part 2.3 二分答案

二分 顾名思义 分成两半 是一种查找算法
比如在有序数组中查找一个数的位置 传统做法是从第一个找到最后一个 这样最坏复杂度是$O(n)$
但是运用二分算法可以将最坏复杂度降到$O(lo{g}_n)$

二分不止在查找中有用 在一些单调问题上 通过二分答案并进行验证 从而通过二分得到答案
很多题目要求在不超过限制代价的条件下求出最优答案，但正向入手却十分困难。如果发现该问题可以反向入手，对于某个确定的答案，可以轻松求出达到该答案所需的代价，则可以枚举答案并判定是否可行。而如果答案具有单调性，即花费代价关于答案单调，则可以通过二分答案加速枚举的过程，从而计算出满足不超过限制的最优答案。

例如一个非常经典的二分答案的应用 解方程

P1024 [NOIP2001 提高组] 一元三次方程求解

传送门
二分法 每次找到一个区间有答案就进行二分

#include
using namespace std;
double a,b,c,d;
double eps=1e-4;
double cal(double x){return a*x*x*x+b*x*x+c*x+d;}
int main(){
    cin>>a>>b>>c>>d;
    for(double i=-100;i<=100;i++){
        double x=cal(i)*cal(i+1);
        if(x>0)continue;
        if(x==0)if(cal(i)==0){printf("%.2lf ",i);continue;}
        if(x<0){
            double l=i,r=i+1;
            while(r-l>eps){
                double mid=(l+r)/2;
                if(cal(l)*cal(mid)>0)l=mid;
                else r=mid;
            }
            printf("%.2lf ",r);
        }
    }
    putchar(10);
}

P2678 [NOIP2015 提高组] 跳石头

传送门
看见最小答案最大这种字样就基本是二分答案的做法了 这题也一样 求最小跳跃距离最大 那么就对最小跳跃距离进行二分

#include
using namespace std;
#define N 50050
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
int l,n,m,le,ri,mid,ans,a[N];
bool check(int dis){
    int mov=0,now=0;
    for(int i=1;i<=n;i++){
        if(a[i]-now<dis)mov++;
        else now=a[i];
        if(mov>m)return false;
    }
    if(l-now<dis)if(mov==m)return false;
    return true;
}
int main(){
    read(l),read(n),read(m);
    for(int i=1;i<=n;i++)read(a[i]);
    le=0,ri=l;
    while(le<=ri){
        mid=le+ri>>1;
        if(check(mid))ans=mid,le=mid+1;
        else ri=mid-1;
    }
    cout<<ans<<endl;
}

P1902 刺杀大使

传送门
题意是每个房间都能到达四周的任意房间 所以想要到达最后一行的每一个房间只要能到达一个最后一行的房间就可以
题干说球整个不对的最大伤害值最小 考虑二分枚举最大伤害值
对于每个伤害值能否从顶部到达底部 考虑用$bfs$进行遍历
时间复杂度$O(nmlo{g}_2^{p_{i,j_{max}}})$
写完看眼题解 有个哥们说这种做法对$p_{i,j_{max}}$要求较高 如果超过$1e9$就要考虑$O(nm)$做法 我只能说这个在扯淡 只要$p_{i,j_{max}}<2^{100}$这个做法都可以 这哥们写的$O(nm)$对不对不知道 兄弟们可以去参观一下

#include
#define N 1100
#define reg register
using namespace std;
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
int l,r,ans,mid,n,m,pnt,vis[N][N],sqr[N][N];
void bfs(int x, int y){
    vis[x][y]=1;
    if(x==n){pnt=1;return ;}
    if(pnt)return ;
    if(!vis[x+1][y]&&sqr[x+1][y]<=mid)bfs(x+1,y);
    if(y>1&&!vis[x][y-1]&&sqr[x][y-1]<=mid)bfs(x,y-1);
    if(y<m&&!vis[x][y+1]&&sqr[x][y+1]<=mid)bfs(x,y+1);
    if(x>1&&!vis[x-1][y]&&sqr[x-1][y]<=mid)bfs(x-1,y);
}
int main(){
    read(n),read(m);
    for(reg int i=1;i<=n;i++){
        for(reg int j=1;j<=m;j++)read(sqr[i][j]);
    }
    l=0,r=1000;
    while(l<=r){
        mid=l+r>>1;
        memset(vis,0,sizeof vis);pnt=0;
        vis[1][1]=true;bfs(1,1);
        if(pnt)ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans<<endl;
}

P1314 [NOIP2011 提高组] 聪明的质监员

传送门
注意到所求式子当$W$越大 $y$越小 因此可以二分枚举$W$ 对每种情况求前缀和从而快速求出$\Sigma y$
如果$\Sigma y>s$那么继续增大$W$ 否则减小$W$

#include
#define N 200020
#define reg register
using namespace std;
typedef long long ll;
inline void read(ll &x){
    ll s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
ll n,m,s,now,ans=1e17,l[N],r[N],w[N],v[N],sum[N],val[N];
bool check(int wei){
    now=0;
    for(int i=1;i<=n;i++){
        if(w[i]>=wei)sum[i]=sum[i-1]+1,val[i]=val[i-1]+v[i];
        else sum[i]=sum[i-1],val[i]=val[i-1];
    }
    for(int i=1;i<=m;i++)now+=(sum[r[i]]-sum[l[i]-1])*(val[r[i]]-val[l[i]-1]);
    ans=min(ans,abs(now-s));
    if(now<s)return true;
    else return false;
}
int main(){
    read(n),read(m),read(s);
    for(reg int i=1;i<=n;i++)read(w[i]),read(v[i]);
    for(reg int i=1;i<=m;i++)read(l[i]),read(r[i]);
    int le=0,ri=1e6,mid;
    while(le<=ri){
        mid=le+ri>>1;
        if(check(mid))ri=mid-1;
        else le=mid+1;
    }
    printf("%lld\n",ans);
}

P1083 [NOIP2012 提高组] 借教室

传送门
不得不说 这个题真的很有前$CSP$时代的$NOIP$特色
区间减 第一眼觉得是线段树树状数组 数据结构都忘了 本来想放弃 一想绿题不能这么难 决定用差分试试
差分最大的问题就是每次查询数组是否有复数元素时需要$O(n)$的复杂度 一共有$m$次操作 时间复杂度时$O(nm)$ 过不去 直到现在还没想明白跟二分有啥关系
后来发现了一个问题 我们可以从通过操作次数上做文章 比如进行$x$个操作时数组有负数
如果进行多于$x$个租用教室操作 那么肯定数组中更有负数
如果进行少于$x$个租用教室操作 那么数组中才有可能没有负数
因此我们可以二分操作次数 然后判断进行这么多次操作次数之后的数组中有没有复数 从而判断该操作次数是否可行
对操作次数进行二分时间复杂度$O(lo{g}_m)$ 加上差分 时间复杂度是$O(nlo{g}_m)，1e6$没问题

#include
#define N 1000020
#define reg register
using namespace std;
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
int n,m,ans,a[N],b[N],c[N],l[N],r[N],num[N];
bool check(int x){
    for(reg int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
    for(reg int i=1;i<=x;i++)b[l[i]]-=num[i],b[r[i]+1]+=num[i];
    for(reg int i=1;i<=n;i++){
        c[i]=c[i-1]+b[i];
        if(c[i]<0)return false;
    }
    return true;
}
int main(){
    read(n),read(m);
    for(reg int i=1;i<=n;i++)read(a[i]);
    for(reg int i=1;i<=m;i++)read(num[i]),read(l[i]),read(r[i]);
    int le=0,ri=m,mid;
    while(le<=ri){
        mid=le+ri>>1;
        if(check(mid))ans=mid,le=mid+1;
        else ri=mid-1;
    }
    if(ans>=m)puts("0");
    else{
        puts("-1");
        cout<<ans+1<<endl;
    }
}

P4343 [SHOI2015]自动刷题机

传送门
裸题二分答案 注意的是本题$check$函数最好返回一个值 因为有两种情况$($当然你写俩$check$也行

#include
#define N 100020
#define reg register
using namespace std;
typedef long long ll;
inline void read(ll &x){
    ll s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
ll l,k,ans,a[N],le,ri,mid;
ll check(ll x){
    ll now=0,sum=0;
    for(int i=1;i<=l;i++){
        now+=a[i];
        if(now>=x)sum++,now=0;
        if(now<0)now=0;
    }
    return sum;
}
int main(){
    read(l),read(k);
    for(int i=1;i<=l;i++)read(a[i]);
    le=1,ri=1e18,ans=0;
    while(le<=ri){
        mid=le+ri>>1;
        if(check(mid)>k)le=mid+1;
        else if(check(mid)<k)ri=mid-1;
        else ans=mid,ri=mid-1;
    }
    if(!ans){puts("-1");return 0;}
    cout<<ans<<" ";
    le=1,ri=1e18,ans=0;
    while(le<=ri){
        mid=le+ri>>1;
        if(check(mid)>k)le=mid+1;
        else if(check(mid)<k)ri=mid-1;
        else ans=mid,le=mid+1;
    }
    if(!ans){puts("-1");return 0;}
    cout<<ans<<endl;
}

总结

现在凌晨$3:18$明早$7:00$做核酸 没啥总结的 我要睡觉