[Oracle] LeetCode 1802 Maximum Value at a Given Index in a Bounded Array
2022/8/24 2:23:15
本文主要是介绍[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 where0 <= i < n
.abs(nums[i] - nums[i+1]) <= 1
where0 <= 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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!