两球之间的磁力

2023-11-06 22:10

文章标签 之间磁力两球

本文主要是介绍两球之间的磁力，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1552. 两球之间的磁力

在这里插入图片描述

分析可知：两球的最小距离的最小为1；最小距离的最大值是 (最后位置的篮子坐标 - 最前位置的篮子的坐标) / (球数-1)，注意这个公式生效的前提是需要对所有的篮子进行升序排序。
要使任意两球间的最小距离最大，我们可从最小距离1开始尝试，直到找到临界值。当然这种方法效率比较低。我们可以使用二分查找。

最后我们需要一个函数来检测当前距离是否符合要求。我们可以从前往后把相邻两个篮子的位子相减，如果大于等于当前距离，那就说明这两个篮子的距离足够放这两个球，下次检测就把后一个篮子作为起始篮子，否则就寻找下一个篮子，检测距离。我们每次检测符合要求就使所放球数加1，如果所放球数等于m就说明当前距离符合要求，如果所有篮子检测完毕都没达到m,就说明当前距离过大，不符合要求。

  
bool check2(vector<int> poisition,int distance,int m)
{int count=1;int j = 0, res = 0;for (int i = 1; i < poisition.size(); i++){if (poisition[i]-poisition[j]>=distance){		count++;j = i;if (count>=m){return true;}}		}return false;
}int maxDistance(vector<int>& position, int m) {sort(position.begin(), position.end());int len = position.size();int min = 1;int max = (position[len-1] - position[0]) / (m - 1);int mid = 0;int rs=1;while (max >= min){mid = (min + max) / 2;if (check2(position, mid, m)){    rs=mid;min = mid + 1;}else{max = mid -1;}}return rs;
}