AcWing 4176. 愤怒的牛
原题链接
简单
作者:
起风了_42
,
2024-03-04 20:36:01
,
所有人可见
,
阅读 17
/*
1.二分可能的最大距离
2.观察这个mid存不存在放完牛之后任意两头之间的距离大于等于这个mid
3.如果存在那么可能还会更大
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 1e5+7;
int a[MAX];
int n,m;
bool check(int mid)
{
int cnt = 1;
int minn = a[1];
for(int i=2;i<=n;i++)
{
if(a[i] - minn >= mid)//这两头牛符合位置 更新最后一个牛的位置 找下一个牛的位置
{
cnt++;
minn = a[i];
}
}
if(cnt >= m)return true;
return false;
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
int l = 0,r = 1e9;
while(l+1<r)
{
int mid = (l+r)>>1;
//可能的最大距离
if(check(mid))
l = mid;
else
r = mid;
}
cout<<l;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);
cout.tie(0);
//cout<<fixed<<setprecision(2);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}