[ACM] poj 2456 Aggressive cows （二分查找）

aggressive cows

time limit: 1000ms

memory limit: 65536k

total submissions: 5436

accepted: 2720

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

sample output

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.

source

解題思路：

這道題雖然不長，可是讀了好幾遍才讀懂。有n個牛舍，每個牛舍有自己的位置xi（可以了解為坐标），把c頭牛放在這n個牛舍裡面，要求最近的兩頭牛之間的最大距離。

比如測試資料 5個牛舍 3頭牛 牛舍坐标1 2 8 4 9

先按貪心，第一頭牛肯定被放在第一個牛舍裡，排序 1 2 4 8 9

第二頭牛可以放在2，也可以放在4，假設第二頭牛放在2 ，與第一頭牛的距離為1 ，假設第三頭放在9，與第二頭的距離為7，那麼，最近的兩頭牛之間的最大距離為1

最有解為 第一頭牛放在1  第二頭牛放在4 ，第三頭牛放在9 ，那麼 4-1=3  9-4=5 ，最近的兩頭牛之間的最大距離為3

也就是求相鄰兩頭牛之間距離的最小值（取最大）。這個距離采用二分的形式進行判斷。

代碼：