luogu-二分基础题单(2020-05-19）

题目列表

p1
p2

下面记录其中几道比较典型的题

P2678.跳石头 + P3853路标设置

这两题都是二分答案，并且check函数非常的类似，对于跳石头那题，如果当前岩石与下一个即将跳到的岩石距离小于二分的答案，则移走它，走完之后判断移走的岩石数目是否小于M即可，对于路标设置那题，思路类似，对于两个路标，如果它们之间的距离超过了二分答案，则在这两个路标之间插入额外的路标，走完之后同样判断一下是否满足条件即可

P2678:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5+100;
//solution:二分答案，然后判断在移走M个岩石后能不能得到答案
//如果可以，则可以让答案更小
//否则，让答案更大

int L,N,M;
int a[MAXN];

bool check(int x){
    int res = 0;   //当前已经移走得岩石数量
    int now = 0;  //当前位子跳到下一个岩石的距离
    for(int i = 1; i<=N; i++){
        if(a[i]-now >= x) now = a[i];
        else{
            //说明当前岩石需要移走
            res ++;
        }
    }
    return res <= M;
}
int main()
{
    
    cin>>L>>N>>M;
    for(int i = 1; i<=N; i++) cin>>a[i];
    a[++N] = L;
    
    int l = 0, r = 1e9;
    while(l<r){
        int mid = (l+r+1)>>1;
        if(check(mid)) l = mid;
        else r = mid-1;
    }
    
    cout<<l<<endl;
    return 0;
}

P3853

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long LL;

using namespace std;
const int N = 1e5+100;

int L,n,k;
int a[N];

bool check(int x){
    int cnt = 0;
    int now = 0;
    for(int i  = 2; i<=n; i++){
        now = a[i]-now;
        if(now > x){
            cnt += now/x;
            if(now%x==0) cnt--;
        }
        now = a[i];
    }
    if(cnt > k) return false;
    else return true;
    return 0;
}

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

P3743.kotori的设备

对-1进行特判：所有设备每秒的能量消耗之和还小于每秒充电获得的能量
二分答案-时间T：对于每个设备来说，如果没有充电器，则Ts后剩余能力为b[i]-a[i]*T，可能为负，如果为负，则需要充电器来充电，如果在某一个设备的充电过程中没电了(给这个设备的充电时间不够了，前面的设备已经占用了充电器一段时间)，那么说明T偏大了，返回true，否则在结束之后返回false

Tip:对于浮点数二分来说，题目对精度要求如果很高的话只使用double的话可能在二分多次之后答案就二分不动了，这样可以使用long double，或者可以限定二分次数(足够)

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long LL;
typedef long double LB;
const int N = 1e5+100;
const double eps = 1e-6;

int n;
LB p;
LB a[N],b[N];

bool check(LB x){
    LB power = x;
    LB t = x;
    
    for(int i = 1; i<=n; i++){
        LB temp = b[i]-a[i]*t;
        if(temp < 0){
            //需要充电才能坚持t秒
            LB dec = temp*(-1)/p;
            if(power>=dec){
                //如果可充就充，否则说明当前时间太大
                power -= dec;
            }else{
                return true;
            }
        }
    }
    
    return false;
}
int main()
{
    IO;
    cin>>n>>p;
    LL dec = 0;
    for(int i = 1; i<=n; i++){
        cin>>a[i]>>b[i];
        dec += a[i];
    } 
    
    if(dec <= p){
        cout<<-1<<endl;
        return 0;
    }
    
    LB l = 0.0, r = 10000000000.0;
    
    while(r-l>eps){
        LB mid = (l+r)/2;
        if(check(mid)) r = mid;
        else l = mid;
    }
    
    cout<<fixed<<setprecision(10)<<l<<endl;
    return 0;
}