问题 A: [二分和三分] 愤怒的牛
时间限制: 1 Sec 内存限制: 128 MB
[命题人: 外部导入]
题目描述
农夫约翰建造了一座有 n 间牛舍的小屋, 牛舍排在一条直线上, 第 i 间牛舍在 xi 的位置, 但是约翰的 m 头牛对小屋很不满意, 因此经常互相攻击. 约翰为了防止牛之间互相伤害, 因此决定把每头牛都放在离其它牛尽可能远的牛舍. 也就是要最大化最近的两头牛之间的距离.
牛们并不喜欢这种布局, 而且几头牛放在一个隔间里, 它们就要发生争斗. 为了不让牛互相伤害. John 决定自己给牛分配隔间, 使任意两头牛之间的最小距离尽可能的大, 那么, 这个最大的最小距离是多少呢?
输入
第一行用空格分隔的两个整数 n 和 m;
第二行为 n 个用空格隔开的整数, 表示位置 xi.
输出
输出仅一个整数, 表示最大的最小距离值.
样例输入 Copy
5 3 1 2 8 4 9
样例输出 Copy
3
提示
把牛放在 1,4,8 这样最小距离是 3
2≤n≤1e5 , 0≤xi≤1e9, 2≤m≤n
解析: 二分距离, judge 函数判断牛的个数.
AC 代码
- #include<cstdio>
- #include <map>
- #include<iostream>
- #include<string>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- using namespace std;
- inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
- typedef long long ll;
- const int maxn=1e6+5;
- int n,m;
- int a[maxn];
- int judge(int x){
- int cnt=1;
- int t=0;
- for(int i=1;i<n;i++){
- if(a[i]-a[t]>=x){
- cnt++;
- t=i;
- }
- }
- if(cnt>=m){
- return 1;
- }
- return 0;
- }
- int main(){
- cin>>n>>m;
- for(int i=0;i<n;i++){
- cin>>a[i];
- }
- sort(a,a+n);
- int l=a[0],r=a[n-1]-a[0];
- int ans;
- while(l<=r){
- int mid=(l+r)/2;
- if(judge(mid)){
- l=mid+1;
- ans=mid;
- }
- else{
- r=mid-1;
- }
- }
- printf("%d",ans);
- }
来源: http://www.bubuko.com/infodetail-3399540.html