进击的奶牛

2023-12-28 21:45:39

题目

进击的奶牛

题意

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

文章来源:https://blog.csdn.net/2301_81135929/article/details/135278176
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。