进击的奶牛

题目

进击的奶牛

题意

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;
}