题解 | 范围内整数的最大得分
题干分析:
依照题意,本题要求我们寻找一个数组中任意两数之间差值的绝对值集合中的最小值的最大值,且数组中的每个元素均可以抬升0~d.
简单来说,就是我们需要尽可能的通过抬升操作,将数组变为各大小差不多的元素间差值尽可能均匀,这样便能够使得集合中最小值取得最大(极端情况下,数组变成等差数列,此时最小值就只有一个,但凡有所偏差均会使最小值更小,导致最小值取不到最大.)
基于以上思想,我们发现这与数组中每个元素的位置无关,且有序能够方便我们的操作,因此首先想到对数组进行排序操作.
排完序后我们思考如何使最小差值尽可能大,已知如果最小差值过大,容易使达到相应值所需抬升的大小过大,因此这在此方面符合单调性,由此我们能够进行二分查找最大分数(最小差值).
算法思路:
我们考虑分数s,如果s符合要求,那么:
只要对于数组除最后一个元素外,满足: x[i + 1] <= x[i] + s <= x[i + 1] + d,且为了尽可能满足,我们让每个符合的值尽可能取最小值,便于让下一个元素达到(此时,两者间差值已经大于分数s,但是无所谓,因为s是最小差值).反之,如果超出范围,则证明s分数不可达.
以上这便是二分的判断逻辑.
至于二分的范围,首先左界是毫无悬念的0,有关右界就是此前分析的如果均匀分布便是最值,因此右界便是((x[n-1] - x[0])/(n - 1) + 1)(加一是为了保证此右界取不到,其实右界你随便设个更大的值甚至INT_MAX应该也能找到,但是为了减少查找次数,所以确定一下右界会更好)
实现代码:
int maxPossibleScore(vector<int>& start, int d) {
ranges::sort(start);
auto chack = [&](const int s) -> bool {
long long x = LLONG_MIN;
for (const int a : start) {
x = max(x + s, static_cast<long long>(a)); // 最小满足值(max是因为少说也得比前一个元素大s,但如果当前范围最小值([a,a+d])大于此值,我们只能取a)
if (x > a + d) return false; // 判断是否超出范围
}
return true;
};
int left = 0, right = (start.back() - start[0] + d) / static_cast<int>(start.size() - 1) + 1;
while (left + 1 < right) {
if (const int mid = left + (right - left) / 2; chack(mid)) left = mid;
else right = mid;
}
return left;
}
复杂度分析:
- 时间复杂度: 排序O(nlog n), 二分模板O(log n),但是判断函数为时间复杂度为O(n),因此为O(nlog n);总计仍为O(nlog n).
- 空间复杂度: 排序O(log n)的运行栈空间消耗,其他为常数额外空间,因此总计为O(log n).