wordpress后台加站点图标,网站制作怎么做让点击高,网站建设功能要求,美工在网站建设中的作用文章目录1. 题目2. 解题1. 题目
在代号为 C-137 的地球上#xff0c;Rick 发现如果他将两个球放在他新发明的篮子里#xff0c;它们之间会形成特殊形式的磁力。 Rick 有 n 个空的篮子#xff0c;第 i 个篮子的位置在 position[i] #xff0c;Morty 想把 m 个球放到这些篮子…
文章目录1. 题目2. 解题1. 题目
在代号为 C-137 的地球上Rick 发现如果他将两个球放在他新发明的篮子里它们之间会形成特殊形式的磁力。 Rick 有 n 个空的篮子第 i 个篮子的位置在 position[i] Morty 想把 m 个球放到这些篮子里使得任意两球间 最小磁力 最大。
已知两个球如果分别位于 x 和 y 那么它们之间的磁力为 |x - y| 。
给你一个整数数组 position 和一个整数 m 请你返回最大化的最小磁力。
示例 1
输入position [1,2,3,4,7], m 3
输出3
解释将 3 个球分别放入位于 14 和 7 的三个篮子
两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。
我们没办法让最小磁力大于 3 。示例 2
输入position [5,4,3,2,1,1000000000], m 2
输出999999999
解释我们使用位于 1 和 1000000000 的篮子时最小磁力最大。提示
n position.length
2 n 10^5
1 position[i] 10^9
所有 position 中的整数 互不相同 。
2 m position.length来源力扣LeetCode 链接https://leetcode-cn.com/problems/magnetic-force-between-two-balls 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
模板套路题极小极大化 就用 二分查找先将所有的位置排序采用set二分查找 最佳的 距离 dis检查是否 可以放下 m 个球折半查找
class Solution {setint pos;
public:int maxDistance(vectorint position, int m) {int l 1, r 1e91, dis, ans;for(auto i : position)pos.insert(i);while(l r){dis (lr)/2;if(canPutM(m, dis)){ans dis;l dis1;}elser dis-1;}return ans;}bool canPutM(int m, int dis){int count 1, p *pos.begin();auto it pos.lower_bound(pdis);while(it ! pos.end() count m)//放下了几个满足dis间距的球{count;p *it;//下一个满足dis要求的it pos.lower_bound(pdis);//二分查找下一个}return count m; //可以放下这么多球}
};1240 ms 98.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
