Living-Dream 系列笔记 第5期

本期主要讲解二分答案的进阶。

例题

T1

二分需要的秒数，在 check 函数中对于每件衣服，若其在 \(x\) 秒内无法自然晒干，则使用烘干机，并令 \(sum\) 加上使用烘干机的秒数，最后判断 \(sum\) 是否 \(\le x\) 即可。

\(Trick\)：二分边界需要按数据范围尽可能开大，不能开小了。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,a,b;
int w[500031];

bool check(int x){
    int sum=0;
    for(int i=1;i<=n;i++){
        int t=w[i]-x*a;
        if(t>0)
            sum+=ceil(t*1.0/b);
    }
    return sum<=x;
}

signed main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) cin>>w[i];
	
	int l=0,r=5e5+1;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid;
	} 
	cout<<r;
	return 0;
}

T2

基本思路与上期例题基本一致，仅需将 \(a\) 数组的每个数都 \(\times 100\) 转换为整数，最后输出 \(L \div 100\) 转换为小数。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,k;
int a[10031],maxx;

bool check(int x){
    int sum=0;
    for(int i=1;i<=n;i++) sum+=a[i]/x;
    return sum>=k;
}

signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        double x;
        cin>>x,a[i]=x*100,maxx=max(maxx,a[i]);
    }
    
    int l=0,r=maxx+1;
    while(l+1<r){
        double mid=(l+r)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    cout<<setprecision(2)<<fixed<<l/100.0;
    return 0;
}

T3

这题是个将最小值最大化的二分，还是考虑二分最近距离的最大值。

在 check 函数中，记录一个变量 \(last\) 保存上一头牛被安放的坐标。循环 \(n\) 个牛棚，若当前牛棚的坐标 \(x_i-last \ge mid\)，则令被安放的牛数 \(y \gets y+1\)，同时更新 \(last \gets x_i\)。最后判断 \(y\) 是否 \(\ge c\) 即可。

#include<bits/stdc++.h>
using namespace std;

int n,c;
int a[100031];

bool check(int x){
    int tot=0,last=-1e9;
    for(int i=1;i<=n;i++)
        if(a[i]-last>=x) tot++,last=a[i];
    return tot>=c;
}

int main(){
    cin>>n>>c;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    
    int l=0,r=a[n]-a[1]+1;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    cout<<l;
    return 0;
}

习题

T1

与上一题类似，二分最短跳跃距离的最大值。

在 check 函数中，记录三个变量：\(sum\)、\(cur\) 和 \(nxt\)，分别表示移除的石头数、当前位置和下一个位置。初始均为 \(0\)。

枚举 \(n\) 个石头，若 \(d_{nxt}-d_{cur} < mid\)，则 \(sum \gets sum+1\)，否则令 \(cur \gets nxt\)。

注意 \(a_{n+1}\) 应当设为 \(L\)（不是二分左端点）。

#include<bits/stdc++.h>
using namespace std;

int s,n,m;
int a[50031];

bool check(int x){
    int nxt=0,cur=0,sum=0;
    while(nxt<=n){
        nxt++;
        if(a[nxt]-a[cur]<x) sum++;
        else cur=nxt;
    }
    return sum<=m;
}

int main(){
    cin>>s>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    a[n+1]=s;
    
    int l=0,r=s+1;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    cout<<l;
    return 0;
}

T2

二分可用时间，在 check 函数中计算在 \(mid\) 时间内会消耗完的充电器需要补充的电量之和，与 \(mid \times p\) 比较即可。

注意保留六位小数。

#include<bits/stdc++.h>
using namespace std;

const double eps=1e-6; 
double n,p;
double a[100031],b[100031];

bool check(double x){
    double s=0.0;
    for(int i=1;i<=n;i++)
        if(a[i]*x>b[i]) s+=(a[i]*x-b[i]);
    return s<=x*p;
}

int main(){
    cin>>n>>p;
    double s=0.0;
    for(int i=1;i<=n;i++) 
        cin>>a[i]>>b[i],s+=b[i];
    if(s<=p){ cout<<-1.000000; return 0; }
    
    double l=0.0,r=1e10;
    while(l+eps<r){
        double mid=(l+r)/2.0;
        if(check(mid)) l=mid;
        else r=mid;
    }
    cout<<setprecision(6)<<fixed<<l;
    return 0;
}