5711. 有界数组中指定下标处的最大值

算法

二分 $O(log maxSum)$

• n = 1e9 数据范围比较大，再加上要求的是一个数值，可以直接二分，转化为判定问题，每次判断将 nums[index] = k 是否满足。下面是判定过程：
• 考虑 0~(index-1) 的范围的赋值情况，一共有 index 个数，我们要尽量给每个数分配较小的值，使得尽量不超过 maxSum。我们最小可以分配到 [1, 2, ..., k - 1] 共 k-1 个数，如果 k-1 >= index，那么我们分配的数是 [k-1-(index-1), ..., k-1] （公差为 1 的等差数列），否则的话，我们分配的数是 [1, 1, ..., 1, 2, ..., k-1]，其中后 k-1 个数构成等差数列，左侧剩下 index-(k-1) 个 1。
• 接着考虑 (index+1)~(n-1) 的范围的赋值情况，实际上可以等价于把数组反转，考虑从 0~(n-1-index) 的情况。因此，单独将上述计算过程抽成函数，用不同参数计算两遍。
• 最后加上 nums[index]，判断和是否不超过 maxSum。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
class Solution {
    int n, idx, mS;
    LL calc(int mid, int idx) {
        LL sum = 0;
        if (mid - idx >= 1) {
            int left = mid - idx;
            sum += (left + mid - 1ll) * idx / 2;
        } else {
            sum += (1ll + mid - 1) * (mid - 1) / 2;
            sum += (idx + 1ll - mid) * 1;
        }
        return sum;
    }
    bool valid(int mid) {
        LL sum = calc(mid, idx) + calc(mid, n - 1 - idx) + mid;
        // cout << mid << " " << calc(mid) << " " << calc(n - 1 - idx) << " " << mid << " " << sum << endl;
        if (sum <= mS) return true;
        return false;
    }

   public:
    int maxValue(int _n, int index, int maxSum) {
        n = _n, idx = index, mS = maxSum;
        int l = 1, r = 1e9;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (valid(mid))
                l = mid;
            else
                r = mid - 1;
        }
        return l;
    }
};