Total Submissions: 24659

Accepted: 11439

Description

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

Input

* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Line i+1 contains an integer stall location, xi

Output

* Line 1: One integer: the largest minimum distance

Sample Input

5 3
1
2
8
4
9

Sample Output

3

Hint

OUTPUT DETAILS:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.

Huge input data,scanf is recommended.

   题意大致是有n个位置，安排m头牛，问牛之间的距离最小值的最大是多少。

  我感觉这和 河里有n块石头，取出m块使得石头之间最小距离的最大是多少差不多吧，无奈我按这个思路并没有做出，我感觉思路没问题啊，可能是我太弱了吧。

AC Code

#include<iostream>
#include<iomanip>
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define PI  3.14159265358979
#define LL long long
#define INF  10000001000
#define  eps   0.00000001
using namespace std;
bool judge(LL x);
LL n,m,k;
LL ans[100010];
bool judge(LL x)
{
    LL cnt=1,temp=ans[1];
    for(LL i=2;i<=n;++i)
    {
        if(ans[i]-temp>=x)
        {
            ++cnt;
            temp=ans[i];
            if(cnt>=m) return 1;
        }
    }
    return false;
}
int main()
{
    //freopen("input.txt","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>ans[i];
    sort(ans+1,ans+n+1);
    LL L=0,R=ans[n]-ans[1];LL mid;LL res;
    while(L<=R)
    {
        mid=(L+R)>>1;
        if(judge(mid)) {res=mid;L=mid+1;}
        else R=mid-1;
    }
    cout<<res<<endl;
}

Wa       整数的二分过程真是不好弄

#include<iostream>
#include<iomanip>
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define PI  3.14159265358979
#define LL long long
#define INF  10000001000
#define  eps   0.00000001
using namespace std;
bool judge(LL x);
LL n,m,k;
LL ans[100010];
int main()
{
    //freopen("input.txt","r",stdin);
    cin>>n>>m;k=n-m;
    for(int i=1;i<=n;++i)
    {
        cin>>ans[i];
    }
    sort(ans+1,ans+n+1);
     LL min_=INF;
     for(int i=2;i<=n;++i)
     {
         min_=min(min_,ans[i]-ans[i-1]);
     }
    ans[n+1]=1000000000000;
    LL L=min_,R=INF/m;LL mid;LL res;
    while(L<R)
    {
        mid=(L+R)>>1;
        if(judge(mid)) {res=mid;R=mid-1;}
        else {L=mid+1;}
    }
    cout<<res<<endl;


}
bool judge(LL x)
{
    LL sum=0;
    for(LL i=2,j=1;i<=n+2;)
    {
        if(ans[i]-ans[j]<x)
        {
            ++sum;
            ++i;
        }
        else {j=i;++i;}
    }
    if(sum>=k) return 1;
    else return 0;
}