题解 | #愤怒的牛#
愤怒的牛
https://ac.nowcoder.com/acm/problem/50171
思路
先将所有牛按位置排序。随后二分间隔的最大值。check的时候如果位置不够加了，那么需要的间隔就加。
代码
#include<bits/stdc++.h>
#define debug(x) cout<<"x="<<x<<endl
#define int long long
using namespace std;
const int maxn=1e5+7;
const int mod=1e9+7;
typedef long long ll;
//ifstream mycin("in.txt");
//ofstream mycout("out.txt");
inline void read(int &data){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
data=x*f;
}
int n,m,a[maxn];
bool check(int x){
int num=1,now=a[1],idx=1;
for(int i=2;i<=n;i++){
if(a[i]-a[idx]>=x) num++,idx=i;
}
if(num>=m) return true;
else return false;
}
signed main(){
read(n);read(m);
for(int i=1;i<=n;i++) read(a[i]);
sort(a+1,a+1+n);
int l=0,r=1e9+7,mid;
while(r-l>1){
mid=l+r>>1;
if(check(mid)) l=mid;
else r=mid;
}
cout<<l<<endl;
return 0;
}
博世一面4人在聊
投递网易等公司10个岗位 >