牛牛有n(2≤n≤105)(2 \leq n \leq 10^5)(2≤n≤105)个玩偶,牛牛打算把这n个玩偶摆在桌子上,桌子的形状的长条形的,可以看做一维数轴。 桌子上有 M 个互不相交的区间(1≤M≤105)(1≤M≤10^5)(1≤M≤105),这些区间上面可以放玩偶。一个位置只能放一个玩偶,玩偶之间的距离越大越美观,牛牛想最大化 D 的值,其中 D 为最近的两个玩偶之间的距离。请帮牛牛求出 D 的最大可能值。

这个题我在考场上第一反应是贪心,但是没想出来
然后我突然联想到了一个比较相似的题
https://www.luogu.com.cn/problem/P2678
我们二分答案,然后进行判断
然后二分答案是logINT_MAX的
所以只要我们判断的复杂度控制在 n+m 内就可以过掉此题
和那到相似的题几乎一样思路判断
贪心!!!!
区间应该提前按照左或者右端点排序(因为区间不相交,所以排序左端点和右端点都一样)


如果要判断x是否是可行答案
第一个玩偶一定是放在最左边的区间的左端点上
以后放玩偶放在与上一个玩偶相距大于等于x最左边(贪心思想,尽量往左边放)的可以放置的位置即可

参考代码

/**
 * struct Interval {
 *    long long start;
 *    long long end;
 *    long longerval(long long s, long long e) : start(start), end(e) {}
 * };
 */

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 
     * @param n long long整型 玩偶数
     * @param m long long整型 区间数
     * @param long longervals long longerval类vector 表示区间
     * @return long long整型
     */
    struct oppo{
        long long l,r;
        bool operator<(const oppo a)const{
            return l<a.l;
        }
    }h[1000005];
    long long N,M;
    bool check(long long x)
    {
        long long now=0;
        long long i=1;
        long long all=N;
        while(all){
            long long k=max(h[i].l,now);
            now=k+x;
            all--;
            if(all==0) break;
            while(h[i].r<now){
                i++;
                if(i>M)
                    return 0;
            }
        }
        return 1;
    }
    int doll(int n, int m, vector<Interval>& intervals) {
        // write code here
        N=n;
        M=m;
        for(long long i=0;i<m;i++)
        {
            h[i+1].l=intervals[i].start;
            h[i+1].r=intervals[i].end;
        }
        sort(h+1,h+m+1);
        long long l=1,r=INT_MAX,mid;
        int ans=0;
        while(l<=r){
            mid=(l+r)/2;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        return ans;
    }
};