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 == nnums[i]is a positive integer where0 <= i < n.abs(nums[i] - nums[i+1]) <= 1where0 <= 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;
}
};