题目链接

https://www.dotcpp.com/oj/problem1846.html

解题思路

二分+贪心。
大思路比较好想，但是贪心思路不好想。
二分移动的距离；
按照区间右端点从小到大排序，每次都先尝试插入未插入中右端点最小的。若此移动距离能让覆盖满区间，此距离可以；反之，不行。
另外值得注意的点：因为存在小数的情况，但是把二分换成double会严重影响复杂度，所以我们先把输入区间的左右端点乘2后再插入，最后输出的时候只需要除2即可。

AC代码

#include<bits/stdc++.h>
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%d",x)
using namespace std;
const int B=20000;
typedef pair<int,int> P;
multiset<P> s;
int check(int mid){
    multiset<P> tmp(s);
    int now=0,flag=0;
    while(!tmp.empty()){
        for(multiset<P>::iterator it=tmp.begin();it!=tmp.end();it++){
            flag=0;//用于记录tmp是否还有可以用来覆盖的区间 
            int tta=(*it).second,ttb=(*it).first;
            if(tta-mid<=now && ttb+mid>=now){//可以移动到跨越now的状态 
                flag=1;
                int len=ttb-tta;
                if(tta+mid>=now) now+=len;
                else now=ttb+mid;
                tmp.erase(it);
                break;//每次必须从tmp的头开始试着往区间里塞 
            }    
        }
        if(now>=B) return 1;
        if(!flag) return 0;
    }
    return 0;
}
int main(){
    int n,a,b,l=0,r=B;
    double ans;
    sc(n);
    for(int i=1;i<=n;i++){
        sc(a);sc(b);
        s.insert(P(b*2,a*2));
    }
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }

    cout<<ans*1.0/2.0;
}