Aggressive cows（二分）

2023-10-10 03:50

文章标签 二分 cows aggressive

本文主要是介绍Aggressive cows（二分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Aggressive cows（二分）

来源：洛谷https://www.luogu.com.cn/problem/SP297

描述：

农夫约翰搭建了一间有N间牛舍的小屋。牛舍排在一条线上，第i号牛舍在Xi的位置。但是他的M头牛对小屋很不满意，因此经常相互攻击。约翰为了防止牛之间相互伤害，因此决定把每头牛都放在离其他牛尽可能远的牛舍。求最近的两头牛之间距离的最大值。

输入格式： t 表示有t组数据，每组数据都由下面格式的数据构成。

第1行: 两个用空格隔开的整数: N和C
第2到n+1行: 每行一个整数xi

输出格式：每组输出一个整数: 最近两头牛之间距离的最大值.

输入

输出

二分模板：

x为所求值，s[i]为单调数组int l=1,r=s[n],mid;//确定范围while(l<=r){mid=(l+r)/2;if(s[mid]>x)l=mid+1;//如果大于所求值，说明大于这个点的所有数都大于所求值，所以上边界到中点+1的位置else r=mid-1;//同理下边界增加到中点-1的位置if(s[mid]==x)return mid;如果找到那么就返回找到它的位置}

思路：

1：对于本题，我先选择一个s[]表示每个牛棚的位置。

2： l代表答案可能取到的最小值，r代表答案可能取到的最大值（对，我觉得很重要一点是要认识到，我们是对答案进行二分，范围随每一步答案的变化而变化）

3:通过不停的对我们期待的答案范围进行二分。当我们此时期待的距离满足的时候，我们可以试着把期待的距离增大一点点l=mid+1，当我们期待的距离不满足的时候，我们试着把期待的距离减小一点点r=mid-1

完整代码：

#include<bits/stdc++.h>
using namespace std;
int t,n,c;//t为多组输入，n代表有n个牛棚，c代表有c个牛
int s[100010];//每个牛棚的位置int check(int a)//a表示我们此时期待的最大距离
{int sum=1;//第一只牛你肯定放在第一个位置int now=s[1];//now代表目前在那个牛棚//一个一个牛棚的遍历，看看符合条件有几个（第一个牛棚已经放了，从第二个牛棚开始）for(int i=2;i<=n;i++){if(s[i]-now>=a)//很好，s[i]牛棚和上一个牛棚的距离达到了我们期待的最大距离{sum++;//又有一只牛能够放进去了now=s[i];//现在牛棚的位置改变}if(sum==c) return 1;//共有c只牛，现在所有的牛都放进去了，太开心了说不定还可以把距离整大点}return 0;//我们期待的距离大了一点，回去把我们期待的距离减小一点试试
}
int main()
{scanf("%d",&t);while(t--){scanf("%d%d",&n,&c);for(int i=1;i<=n;i++){ scanf("%d",&s[i]);} sort(s+1,s+1+n);int l=1;//假设的最小答案为1int r=s[n];//假设最大答案为s[n]int mid;//不停二分求解，直到范围内没有值while(l<=r){mid=(l+r)/2;if(check(mid)) l=mid+1;//如果mid都可以，说明mid之前都可以else r=mid-1;//如果mid都不行，说明mid后面都不行}printf("%d\n",r);//或者输出printf("%d\n",l-1);都可以}return 0;
}