diff options
Diffstat (limited to 'other/max_value_give_idx.cpp')
-rw-r--r-- | other/max_value_give_idx.cpp | 43 |
1 files changed, 0 insertions, 43 deletions
diff --git a/other/max_value_give_idx.cpp b/other/max_value_give_idx.cpp deleted file mode 100644 index ee6c25f..0000000 --- a/other/max_value_give_idx.cpp +++ /dev/null @@ -1,43 +0,0 @@ -// 1802. Maximum Value at a Given Index in a Bounded Array -#include "leetcode.h" - -/* - * given three positive integers: 'n, index, and max_sum'. 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 'max_sum' - * - nums[index] is maximised - * return 'nums[index]' of the constructed array. note that 'abs(x)' equals 'x' - * if 'x >= 0' and '-x' otherwise - */ - -class Solution { - bool check(int n, int i, int max_sum, int m) { - for (int d = 1; max_sum >= 0 && d < m && i + d < n; ++d) - max_sum -= m - d; - for (int d = 1; max_sum >= 0 && d < m && i - d >= 0; ++d) - max_sum -= m - d; - return max_sum >= 0; - } - -public: - int maxValue(int n, int index, int max_sum) { - int left = 0, right = max_sum; - while (left < right) { - int mid = (left + right + 1) / 2; - if (check(n, index, max_sum - n - mid, mid)) - left = mid; - else - right = mid - 1; - } - return left + 1; - } -}; - -int main() { - Solution obj; - printf("%d\n", obj.maxValue(4, 2, 6)); // expect: 2 - printf("%d\n", obj.maxValue(6, 1, 10)); // expect: 3 -} |