北大ACM2456――Aggressive cows~~二分搜索
来源：程序员人生 发布时间：2015-08-17 08:59:33 阅读次数：3880次
这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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
