牛牛摆玩偶_牛客博客

分析

这个题我在考场上第一反应是贪心，但是没想出来然后我突然联想到了一个比较相似的题
https://www.luogu.com.cn/problem/P2678
我们二分答案，然后进行判断然后二分答案是 $log$ ( $图片说明$ )的所以只要我们判断的复杂度控制在 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;
    }
};