二分+贪心

lc3449

二分+贪心

二分答案，在步数限制内，求能达到的最大最小分数

class Solution {
public:
long long maxScore(vector<int>& points, int m) {
auto check = [&](long long low) -> bool {
int n = points.size(), rem = m, pre = 0;
for (int i = 0; i < n; i++) {
int k = (low - 1) / points[i] + 1 - pre; // 还需要操作的次数
if (i == n - 1 && k <= 0) { // 最后一个数已经满足要求
break;
}
k = max(k, 1); // 至少要走 1 步
rem -= k * 2 - 1; // 左右横跳
if (rem < 0) {
return false;
}
pre = k - 1; // 右边那个数顺带操作了 k-1 次
}
return true;
};

long long left = 0;
long long right = 1LL * (m + 1) / 2 * ranges::min(points) + 1;
while (left + 1 < right) {
long long mid = left + (right - left) / 2;
(check(mid) ? left : right) = mid;
}
return left;
}
};