北大ACM2456――Aggressive cows~~二分搜索
來源：程序員人生 發布時間：2015-08-17 08:59:33 閱讀次數：4037次
這1題，也是簡單的2分搜索，求解放置的牛之間的距離盡量遠，也就是最大化最小值。
主要的1步就是將第i頭牛放在了x[j]的位置中,第i + 1
頭牛就要放在滿足x[j] + d < x [k]，k的最小值。
下面是AC的代碼：
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int X[100005];
bool C(int x)
{
int last = 0;
for(int i = 1; i < M; i++)
{
int cur = last + 1;
while(cur < N && X[cur] - X[last] < x) //滿足X[last] + x > X[cur]的最小的cur。
{
cur++;
}
if(cur == N)
return false;
last = cur;
}
return true;
}
void solve()
{
sort(X, X + N);
int left = 0, right = 10000000; //距離在0到10000000之間搜索
while(left + 1 < right) //2分搜索
{
int mid = (left + right) / 2;
if(C(mid))
left = mid;
else
right = mid;
}
cout << left << endl;
}
int main()
{
while(cin >> N >> M)
{
for(int i = 0; i < N; i++)
cin >> X[i];
solve();
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
