C/C++教程

[Oracle] LeetCode 1802 Maximum Value at a Given Index in a Bounded Array

本文主要是介绍[Oracle] LeetCode 1802 Maximum Value at a Given Index in a Bounded Array，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

You are given three positive integers: n, index, and maxSum. You want to construct an array nums (0-indexed) that satisfies the following conditions:

  • nums.length == n
  • nums[i] is a positive integer where 0 <= i < n.
  • abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.
  • The sum of all the elements of nums does not exceed maxSum.
  • nums[index] is maximized.

Return nums[index] of the constructed array.

Solution

二分答案。从贪心的角度出发，我们可能构成的序列，必须是以 \(index\) 为中心，然后左右都是等差数列直到 \(1\).

点击查看代码 
class Solution {
private:
    #define ll long long
    bool check(ll val, int n, int idx, ll maxSum){
        int N_left_to_idx = idx;
        int N_right_to_end = (n-1)-(idx+1)+1;
        
        int AP_series = val-1; // from 1 to val-1
        int N_left_ones = 0, N_right_ones = 0;
        ll leftsum=0, rightsum=0;
        
        if(N_left_to_idx>=AP_series){
            // can contain the whole AP series
            leftsum = (val-1)*val/2;
            N_left_ones = N_left_to_idx - AP_series;
        }
        else{
            // cannot contain the whole AP series
            // AP starts from val-1 to val-idx
            leftsum = N_left_to_idx * (val-1+val-idx)/2;
        }
        
        if(N_right_to_end >= AP_series){
            rightsum = (val-1)*val/2;
            N_right_ones = N_right_to_end - AP_series;
        }
        else{
            rightsum = N_right_to_end*(val-1+val-N_right_to_end)/2;
        }
        return rightsum+leftsum+N_left_ones+N_right_ones+val<=maxSum;
        
    }
public:
    int maxValue(int n, int index, ll maxSum) {
        ll l = 1, r = maxSum;
        int ans=0;
        while(l<=r){
            ll mid = (r-l)/2+l;
            if(check(mid, n, index, maxSum)){
                ans=mid; l=mid+1;
            }
            else r=mid-1;
        }
        return ans;
    }
};
这篇关于[Oracle] LeetCode 1802 Maximum Value at a Given Index in a Bounded Array的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航