信息学奥赛一本通T1433：二分与三分 愤怒的牛

【题目描述】农夫 John 建造了一座很长的畜栏，它包括 N(2≤N≤100,000) 个隔间，这些小隔间依次编号为 x1,...,xN(0≤xi≤1,000,000,000). 但是，John 的 C(2≤C≤N) 头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离

信息学奥赛一本通T1433：愤怒的牛

【题目描述】

农夫 John 建造了一座很长的畜栏，它包括 N(2≤N≤100,000) 个隔间，这些小隔间依次编号为 x1,...,xN(0≤xi≤1,000,000,000). 但是，John 的 C(2≤C≤N) 头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢

【输入】

第一行：空格分隔的两个整数 N 和 C；

第二行---第 N+1 行：i+1 行指出了 xi 的位置。

【输出】

一个整数，最大的最小值。

【输入样例】

5 3
1 2 8 4 9

【输出样例】

3

【源程序】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 100001
#define MOD 123
#define E 1e-6
using namespace std;
int n,c;
int stall[N];
bool judge(int x) {
    int temp=stall[0];
    int cnt=1;
    for(int i=1; i<n; i++) {
        if(stall[i]-temp>=x) {
            cnt++;
            temp=stall[i];
            if(cnt>=c)
                return true;
        }
    }
    return false;
}
int main() {
    scanf("%d%d",&n,&c);
    for(int i=0; i<n; i++)
        scanf("%d",&stall[i]);

    sort(stall,stall+n);

    int left=0,right=stall[n-1]-stall[0];
    while(left<=right) {
        int mid=(left+right)/2;
        if(judge(mid))
            left=mid+1;
        else
            right=mid-1;
    }

    printf("%d\n",right);

    return 0;
}

 

信息学奥赛一本通T1433：二分与三分 愤怒的牛 归属于 二分与三分，更多同类题解源程序见：二分与三分 和 愤怒的牛

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
不写代码的码农
轩爸

0 篇文章

作家榜 »

  1. admin 2 文章
  2. 张芳 0 文章
  3. hanna 0 文章
  4. Jason 0 文章
  5. lixiaioqian 0 文章
  6. GeraldWrora 0 文章
  7. 董伟 0 文章
  8. 信奥达人 0 文章

轩爸

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！