[二分] [POJ] 2456 Aggressive cows
程序员文章站
2022-06-17 19:52:30
...
网上都是二分搜索答案
其实过程也可以二分搜索
洛谷有个扔瓶盖
一样的
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 50;
int cow[MAXN] = {0};
int dis[MAXN] = {0};
int N, C, t, ans = 0;
bool find(int len)
{
if(cow[0] + ( (C - 1) * len) <= cow[N - 1])
{
int mol = C - 1;
int rit = cow[0];
while(mol--)
{
if(rit + len > cow[N - 1])
return false;
rit = cow[lower_bound(cow, cow + N, rit + len) - cow];
}
return true;
}
else
return false;
}
bool bsearch ()
{
int fst = 0, lst = ((cow[N - 1] - cow[0]) / C) + 1, mid;
while(fst <= lst)
{
mid = (fst + lst) / 2;
if(find(mid))
fst = mid + 1;
else
lst = mid - 1;
}
cout<<fst - 1<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin>>N>>C;
for(int i = 0; i < N; i++)
{
cin>>cow[i];
}
sort(cow, cow + N);
bsearch();
return 0;
}