poj 2456 最小值最大化

poj 2456 最小值最大化

 

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

Hi

/**
poj 2456   最小值最大化
題目大意：在編號為a0~an的n個點上放m個棋子要求如何防止能使距離最近的兩個棋子的距離最大
解題思路：二分查找可行的值，貪心：對於每個可行值判斷是否能在n個點中挑出m個。
          貪心的時候應該注意，我們只要從第一個開始就可以了，如果找不出來那麼以第二個以及更後的開始就更找不出來了，因此每次貪心每個點最多考慮
          1次，復雜度O(n)
*/
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=100003;

int a[maxn];
int n,c;

bool greed(int x)
{
    int cn=0;
    int p=a[0];
    for (int i=1; i=p+x)
        {
            cn++;
            p=a[i];
        }
    }
    if (cn>=c-1)
        return true ;
    return false ;
}

int main()
{
    while(~scanf(%d%d ,&n,&c))
    {
        for(int i=0; i