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;
}