LeetCode 二分算法 范围内整数的最大得分

范围内整数的最大得分

给你一个整数数组 start 和一个整数 d，代表 n 个区间 [start[i], start[i] + d]。
你需要选择 n 个整数，其中第 i 个整数必须属于第 i 个区间。所选整数的 得分 定义为所选整数两两之间的 最小 绝对差。
返回所选整数的 最大可能得分 。
示例 1：
输入： start = [6,0,3], d = 2
输出： 4
解释：
可以选择整数 8, 0 和 4 获得最大可能得分，得分为 min(|8 - 0|, |8 - 4|, |0 - 4|)，等于 4。
示例 2：
输入： start = [2,6,13,13], d = 5
输出： 5
解释：
可以选择整数 2, 7, 13 和 18 获得最大可能得分，得分为 min(|2 - 7|, |2 - 13|, |2 - 18|, |7 - 13|, |7 - 18|, |13 - 18|)，等于 5。
提示：
2 <= start.length <= 105
0 <= start[i] <= 109
0 <= d <= 109

题解

我们可以看到，题目要求得分的最大值

而得分是所有两数差的最小值

也就是最小值的最大值，所以我们对得分采用二分算法，二分得到最大的得分

首先确定二分的边界，也就是得分的边界

最小值是 0 ，因为绝对值大于等于0

最大值是数组 start 中的最大值 + d

接着，对于一个得分 m ，我们要如何进行二分

• 假设一个当前某一个区间的数为 x0
• 要使得分为 m ，则下一个数 x1至少为 x0 + m
• 假如 x0 + m 在下一个数的区间[ x1 , x1+d ]内，则此区间内的数取为 x0 + m
• else if x0 + m > x1 + d 说明不可能让得分为 m ，需要将右边界置为 m-1
• else if x0 + m < x1 则下一个区间的数取为 x1
• 如果数组 start 中的所有数据都可以得到得分 m
• 那么 m就是一个可能的值，记录下来，将左边界置为m+1

上述步骤中，对于下一个数的取值，永远是大于等于前一个数，这样就可以避免绝对值的两端讨论

但是要使这样的操作是正确的，前提是数组中的数据是升序的，这样下一个数的取值才是永远大于前一个数的

所以首先对数组 start 进行排序

对于第一个数 x0 的取值，因为要获得m得分，下一个数的取值要 >= x0+m，所以 x0 越小，下一个数的取值就越有可能满足条件，所以 x0 就是 strat[ 0 ]

代码如下↓

int maxPossibleScore(int* start, int startSize, int d) {
    int cmp(void const* a,void const* b)
    {
        return *(int*)a - *(int*)b;
    }
    qsort(start,startSize,sizeof(int),cmp);
    long long l=0,r=start[startSize-1]+d;
    int res=0;
    while(l<=r)
    {
        long long m=(l+r)/2;
        long long x=start[0];
        int f=1;
        for(int i=1;i<startSize;i++)
        {
            x+=m;
            if(x>start[i]+d)
            {
                r=m-1;
                f=0;
                break;
            }
            else
            {
                if(x<start[i])
                {
                    x=start[i];
                }
            }
        }
        if(f)
        {
            res=m;
            l=m+1;
        }
    }
    return res;
}