【hdu2456】aggresive cow——二分

题目：

Aggressive cows

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9488		Accepted: 4716

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.

Source

USACO 2005 February Gold

描述：在一维数轴上选择n个数可以接受对象，有c个对象，要求分配对象使相邻两个数的距离最大，且不相邻。

题解：先对n个数排序，之后求出间距的最大值，然后二分枚举间距尝试即可。

代码：

#include 
#include 
#include 
using namespace std;const int N = 100005;
int arr[N];
int n, c;bool jdg(int x)
{int num = arr[0];int i, j;j = 0;for (i = 1; i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！