1802. Maximum Value at a Given Index in a Bounded Array

這題我有寫出一種Greedy的作法, 但會TLE

class Solution {
public:
    int maxValue(int n, int index, int maxSum) {
        if(n == maxSum) return 1;
        int res = 1;
        int sum = n;
        int left = index;
        int right = index;
        while(true){
            sum = sum + (right - left + 1);
            if(sum > maxSum) break;
            res++;
            if(left > 0) left--;
            if(right <n - 1) right++;
        }
        return res;
    }
};

實際這題是要用到binary search

但我覺得這蠻難想到的XD

[4, 5, 4, 3, 2, 1, 1, 1 ,1]

上面是一組可能的組合, 可以注意到我們只需要看index的位置, 可以用binary search決定值從 [1 … maxSum], 然後我們再檢查就好了

怎麼檢查呢? 我們可以看上面是一個向左右的遞減陣列, 針對左邊跟右邊, 我們可以用小學學的上底加下底 乘高 除2來決定全部的值, 還沒到底的都補1

class Solution {
public:
    bool check(int length, int index, int maxSum, int maxValue){
        long left = max(1, maxValue - index);
        long right = max(1, maxValue - length + index + 1);
        int c1 = 0;
        int c2 = 0;
        if(left == 1){
            c1 = 1 - maxValue + index;
        }
        if(right == 1){
            c2 = length - maxValue - index;
        }
        return (maxValue + left) * (maxValue - left + 1) / 2 + (maxValue + right) * (maxValue- right + 1) / 2 - maxValue + c1 + c2 <= maxSum; 
    }
   
    int maxValue(int n, int index, int maxSum) {
        if(n == maxSum) return 1;
        int res = 1;
        int sum = n;
        int b = 1;
        int t = maxSum;
        while( b <= t){
            int mid = (b + t) / 2;
            if(check(n, index, maxSum, mid)){
                b = mid + 1;
            }else{
                t = mid - 1;
            }
        }
      
        return t;
    }
};