2391.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2391 on 2006-09-28 at 15:59:28 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 102400;

int main()
{
	int n, c, p[N];
	
	while(scanf("%d %d", &n, &c) != EOF) {
		for(int i = 0; i < n; i++) scanf("%d", &p[i]);
		sort(p, p+n);
		int l = 0, h = p[n-1]-p[0];
		while(h != l) {
			int mid = (h+l+1)/2, cn = 1, prev = p[0];
			for(int i = 1; i < n; i++)
				if(p[i]-prev >= mid) { cn++; prev = p[i]; }
			if(cn >= c) l = mid;
			else h = mid-1;
		}
		printf("%d\n", h);
	}
	
	return 0;
}