进击的奶牛

题目

进击的奶牛

题意

1. 通过二分查找算法找到一个最小间距x，使得在数组a中选出的k个数两两之间的间距都不小于x，并且x尽可能大。最后输出这个最大的x值。

思路

1. 程序通过循环依次获取了n个整数，存储在数组a中。
2. .然后，程序对数组a进行了排序，以便进行二分查找。
3. 接着，程序使用二分查找算法来寻找满足条件的最小间距。在二分查找的过程中，通过调用check函数来判断当前的间距m是否满足条件。
4. 在check函数中，程序遍历数组a，计算相邻元素之间的间距，并统计满足条件的间距数量。
5. 最后，程序输出满足条件的最小间距ans。

坑点

1. l和r边界问题

算法一：二分

实现步骤

1. 程序通过循环依次获取了n个整数，存储在数组a中。
2. .然后，程序对数组a进行了排序，以便进行二分查找。
3. 接着，程序使用二分查找算法来寻找满足条件的最小间距。在二分查找的过程中，通过调用check函数来判断当前的间距m是否满足条件。
4. 在check函数中，程序遍历数组a，计算相邻元素之间的间距，并统计满足条件的间距数量。
5. 最后，程序输出满足条件的最小间距ans。

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,a[100010],ans;
bool check(int x)
{int d=a[1],sum=1;for(int i=2;i<=n;i++){if(a[i]-d>=x){sum++;d=a[i];} }return sum>=k;
}
int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}int l=1,r=1e9;sort(a+1,a+n+1);while(l<=r){int m=l+r>>1;if(check(m)){ans=m;l=m+1;}else{r=m-1;}}cout<<ans;return 0;
}