NYOJ 586狂牛病&POJ 2456(二分検索+欲張り)

狂牛病
時間制限:
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

この問題を始めたとき、ずっと意味が分からなかった.それからチームメートに聞いてやっと問題の意味が分かった.原題リンク:http://poj.org/problem?id=2456
表題するのは、C頭牛をN個の番号付き仕切りに入れ、任意の2頭牛が位置する仕切り番号の最小差を最大にすることである.例えば、サンプルの順序付けが完了すると1 2 4 8 9になり、1位置に1頭の牛、4位置に1頭の牛が配置され、それらの差は3である.最後の牛は8または9の位置に置いてもよく、4の位置との差はそれぞれ4、5、1の位置の差はそれぞれ7と8で、3より小さくないので、最大の最小値は3です.
解析:これは最小値を最大化する問題です.まず、仕切り番号を小さいものから大きいものに並べ替えると、最大距離は両端の2頭の牛の差を超えず、最小値は0になります.だから、最小値を2分列挙することで求めることができます.現在の最小値がxであると仮定し、最小差がxであると判断した場合、C頭牛を置くことができ、まずxを大きくしてから判断する.入れられない場合は、現在のxが大きすぎることを説明し、xを小さくしてから判断します.最大のxを求めるまでが最終的な答えです.

#include<stdio.h>
#include<algorithm>
using namespace std;
const int N = 100005;
int a[N], n, c;

bool judge(int x)
{
    int cnt = 1, tmp = a[0];
    for(int i = 1; i < n; i++)
    {
        if(a[i] - tmp >= x)
        {
            cnt++;
            tmp = a[i];
            if(cnt >= c) //    C  
                return true;
        }
    }
    return false;
}

int get_ans() //       
{
    int l = 0, r = a[n-1] - a[0];
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(judge(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    return l - 1;
}

int main()
{
    while(~scanf("%d%d",&n,&c))
    {
        for(int i = 0; i < n; i++)
            scanf("%d",&a[i]);
        sort(a, a+n);
        printf("%d
",get_ans());
    }
    return 0;
}