最小値最大化問題(欲張りシリーズ)

狂牛病
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
4
説明
農夫Johnは、N(2<=N<=100000)個の仕切りを含む長い畜舎を建て、これらの小さな仕切りはx 1の順に番号が付けられています.xN (0 <= xi <= 1,000,000,000).
しかし、ジョンのC(2<=C<=N)頭牛たちはこのようなレイアウトが好きではなく、数頭の牛を1つの仕切りに置くと、争いが起こる.牛同士を傷つけないように.ジョンは自分で牛に仕切りを割り当てて、任意の2頭の牛の間の最小距離をできるだけ大きくすることにした.では、この最大の最小距離は何だろうか.
入力
複数組のテストデータがあり、EOFで終了します.
1行目:スペースで区切られた2つの整数NとC
2行目-N+1行目:xiの位置をそれぞれ指摘
しゅつりょく
テストデータのセットごとに整数を出力し、問題の最大の最小値を満たし、改行に注意します.
サンプル入力

5 3
1
2
8
4
9

サンプル出力

3

ソース
POJ翻訳
アップロード者
TC_張友誼
最小化の問題または最小化の問題
アルゴリズムの考え方:二分+貪欲
考え方:a.牛を並べ替えるb.最初の牛をx 0 c.i番目の牛をxに入れたらniu

 
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

int a[100005];
int n,c;

int ok(int k)
{
    int cnt=1;
    int tmp=a[0];
    for(int i=1;i<n;i++)
    {
        if(a[i]-tmp>=k)
        {
            tmp=a[i];
            cnt++;
            if(cnt>=c)//  c  
            return true;
        }
    }
    return false;
}

int main()
{
        while(~scanf("%d%d",&n,&c))
        {
            for(int i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            sort(a,a+n);
    /*    */
            int l=0,r=a[n-1];
            int mid;
            while(l<=r)
            {
                mid=(l+r)/2;

                if(ok(mid))
                    l=mid+1;
                else
                    r=mid-1;
            }
            printf("%d
",r);
        }
}