簡易題敘#
有 \(n\) ( \(2 \le n \le 10^4\) ) 個牛欄位於 \(0\) 到 \(10^9\) 的座標軸上，你要將 \(k\) ( \(2 \le k \le n\) ) 隻牛放到牛欄中，使得牛之間的最小距離盡量大。
範例測資：
- 輸入
6 3
2 5 7 11 15 20
- 輸出
9
概念講解#
建議解這題之前，先看看這題。
跟上面那題不一樣的是，現在我們要最大化最小距離，所以要特別注意在while迴圈裡更新 \(l\) 跟 \(r\) 時，放得下所有牛的時候更新的是 \(l\) (
越小越有機會放得下 )，反之是 \(r\)。
check函式的部分，預設第一隻牛在 \(a[0]\) ，用 \(now\) 紀錄上隻牛在哪，若超過最小距離限制 \(dis\) ，就更新 \(now\) ，已經放的牛總數 \(cnt\) 加一。最後再檢查有沒有放完 \(k\) 隻牛即可。
範例程式碼#
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 5;
int n, k, a[N];
bool check(int dis) {
int now = a[0], cnt = 1;
for (int i = 1; i < n; i++) {
if (a[i] - now > dis) {
now = a[i];
cnt++;
}
}
return cnt >= k;
}
signed main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int l = 0, r = 1e9 + 1;
while (r != l + 1) {
int mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
cout << r << '\n';
}
