信息学奥赛一本通T1433-愤怒的牛(二分查找求数组的最大值的最小值)

解题思路:

https://blog.csdn.net/xrr233/article/details/106999537

注意事项:

参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

const int MAXN = 1e5;

int data[MAXN] = {};

int main(){

    int n, c;cin >> n >> c;

    for (int i=0; i<n;i++)cin>>data[i];

    sort(data, data+n);

    //二分

    int left = 0;

    int right = data[n-1]-data[0];

    int mid;

    while (left<=right) 

    {

        mid = (right+left)/2;

        int cows = 1;//记录牛数量

        int prev = data[0];//上一个牛所在的栏

        for ( int i=1; i<n; i++) 

        {

            if (data[i]-prev>=mid)

            {

                //符合要求，放一头牛

                cows++;

                prev = data[i];

                if (cows>=c)  break;

            }

        }

        if (cows >= c) left = mid+1;

        else right = mid-1;

    }

    cout << right << endl;

    return 0;

}

或者

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 100005;

int p[N], n, c;

bool judge(int x)

{

    int cnt = 1, prev = p[0];

    for(int i = 1; i < n; i++)

    {

        if(p[i] - prev >= x)

        {

            cnt++;

            prev = p[i];

            if(cnt >= c)    //可以放下C头牛

                return true;

        }

    }

    return false;

}

int main()

{

    int i,left,right,mid;

    cin>>n>>c;

    for(i=0;i<n;i++)cin>>p[i];

    sort(p,p+n);

    right=p[n-1]-p[0];

    left=0;

    while(left<=right)

    {

         mid=(left+right)/2;

         if (judge(mid)) left=mid+1;

         else right=mid-1;

    }

   cout<<right<<endl;

   return 0;

}