http://lx.lanqiao.cn/problem.page?gpid=T451

题意是给定n<=10000个区间，保证总长度大于等于10000，有重叠，让求最大移动的最小值是多少。

首先这个问法就很二分，但是check的方法不好想。

wjjj随便猜了个结论就猜对了（%%%）。二分后按照b排序，优先选b小的。

因为二分出mid后，对于任意一个区间，只能在[a-mid,b+mid]里移动。所以最开始假设没有覆盖，当前点k=0，从左到右选出可以覆盖的区间，尽量往右放进行覆盖，覆盖完以后k移动到本次覆盖区间的最右边。在多个区间都可以覆盖当前点k的时候，b小的肯定在向右移动的时候不是最优解，因为它无论如何都比比它b大的移动得多。最后如果找不到方案可以覆盖完整个区间就说明答案太小，否则答案可能太大。至于小数，可以证明只会有0.5出现，因为最开始的区间都是整数，如果有一个区间移动了1/3那么必然有一个区间需要移动2/3。肯定不是最优解。既然只有0.5那直接把区间长度扩大一倍，规定只能移动整数距离，最后答案half就可以了。

在查找b的时候不能暴力找，否则会炸掉，可以用二分来找，但是注意标记已经用过的区间，我直接用了multiset方便删除用过的区间，复杂度都是logN。总复杂度Nlog²N

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-12;
const int N=20000;
vector<pii> ab;
int vis[10001];
multiset<pii> c2;
int line[10001]; 
int main()
{
    int n,a,b;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        a*=2;b*=2;
        c2.insert({b,a});
    }
    int l=0,r=N;
    while(r>l)
    {
        multiset<pii> c1(c2);
        int mid=(l+r)>>1;
        int now=0;
        while(1)
        {
            int flag=0;
            multiset<pii>::iterator it;
            for(it=c1.begin();it!=c1.end();it++)
            {
                pii tmp=*it;
                int tta=tmp.second,ttb=tmp.first;
                if(tta-mid <= now && ttb+mid >= now)
                {
                    flag=1;
                    int len=ttb-tta;
                    if(now<=tta+mid) now+=len;
                    else now=ttb+mid;
                    c1.erase(it);
                    break;
                }
            }
            if(!flag || now>=N) break;
        }
        if(now>=N) r=mid;
        else l=mid+1;
    }
    double ans=l*1.0/2.0;
    cout<<ans;
}