牛牛摆玩偶(二分)

牛牛摆玩偶(二分)

思路

因为答案具有单调性，所以考虑二分，总是忘记有二分这个优化的玩意了，然后循环判一下，开始点为最左区间起点，然后贪心的选，如果不在某个区间内，就将$pos$定位到下一个区间的左端点即可。

代码

/**
 * struct Interval {
 *    int start;
 *    int end;
 *    Interval(int s, int e) : start(start), end(e) {}
 * };
 */
typedef long long ll;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 玩偶数
     * @param m int整型 区间数
     * @param intervals Interval类vector 表示区间
     * @return int整型
     */
    int doll(int n, int m, vector<Interval>& a) {
         sort(a.begin(),a.end(),[&](Interval a,Interval b){
             return a.start<b.start;
         });
           ll l=1,r=1LL*1e10;
        ll ans=0;
         while(l<=r){
             ll mid=l+r>>1;
             int f=1,now=0;
             ll p=a[now].start+mid;
             for(int i=2;i<=n;i++){
                 while(now<m&&p>a[now].end) now++;
                 if(now>=m){
                     f=0;break;
                 }
                 p=max(p+mid,a[now].start+mid);
             }           
             if(f) l=mid+1,ans=mid;
             else r=mid-1;
         }
        return (int)ans;
    }
};