leetcode1552.兩球之間的磁力
題目鏈接
演算法
二分+貪心
時間復雜度O(nlogn + nlogm)
1.根據題意描述，我們需要將m個球放入到n個籃子中，根據題目中資料范圍描述發現m <= n，故可以將一個球放入到一個籃子中，這道題主要就是要求出相鄰的兩個球之間的距離的最小值，而且要盡可能的讓這個最小值最大化
2.分析完了題意，下面來分析一下如何解題，剛開始的思路是首先排序，然后將第一個球放到陣列的第一個位置，然后根據剩余的球的個數列舉球的位置，但因為還需要記錄相鄰兩個球的距離差，如果這樣純暴力的話寫起來太過于繁瑣，并且耗時大，最終該思路未果，在搜索了大佬們的解題思路后，了解到可以使用二分思想來對磁力進行二分，具體思路如下，
3.對于一些球，它們之間磁力的最大值是poisiton陣列中元素的最大值減去最小值(這里先不考慮球的個數)，那么我們就可以確定了磁力的區間范圍[l,r]，然后將[l,r]劃分為[l,mid-1]、[mid,r]，為什么要這樣劃分呢，因為題目中說了要最大化最小磁力，所以我們要盡可能的使得mid更大，劃分條件就是判斷position陣列是否能夠找到m個籃子使得它能夠滿足相鄰的兩個球之間的距離大于等于mid，如果滿足，則l=mid，否則r=mid-1，
4.為了使得最小磁力最大化，我們可以使其中一個球位于最左邊的那個籃子里，然后再以此列舉球的位置，使得相鄰的兩個球的距離大于等于mid，
5.由此，這道題的總體思路是：先排序，然后二分，
C++代碼
class Solution {
public:
int maxDistance(vector<int>& position, int m) {
sort(position.begin(), position.end());
int len = position.size();
int l = 1, r = position[len - 1] - position[0];
while(l < r){
int mid = l + r + 1>> 1;
if(check(mid, position, m))
l = mid;
else
r = mid - 1;
}
return l;
}
bool check(int k, vector<int>& position, int m){
int len = position.size();
int last = position[0]; //last用于記錄上一個存放球的籃子的位置
int t = 1; //記錄已經放入到籃子的球的個數
for(int i = 1; i < len; i++){
if(position[i] - last >= k){
++t;
last = position[i];
if(t == m) return true;
}
}
return false;
}
};
這道題使用的二分模板來源于yxc大佬的二分查找演算法模板
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/118208.html
標籤：其他
下一篇：相同網段的網路如何互聯