pku2456.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 63 行

#include <stdio.h>
#include <algorithm>
using namespace std;

const int size = 100001;
int p[size];
int N, C;

int Calc(int x)
{
	int cnt = 1;
	int i, last;
	last = p[0];
	for (i = 1; i < N && cnt <= C; i++)
	{
		if (p[i] - last >= x)
		{
			cnt++;
			last = p[i];
		}
	}
	return cnt;
}

int main()
{
	int i, tmp;
	int min, max, mid;
	while (scanf("%d %d", &N, &C) != -1)
	{
		for (i = 0; i < N; i++)
		{
			scanf("%d", &p[i]);
		}
		sort(p, p + N);
		min = 0;
		max = (p[N - 1] - p[0]) / (C - 1) + 1;
		while (min + 1 < max)
		{
			mid = (min + max) >> 1;
			tmp = Calc(mid);
			if (tmp >= C)
			{
				min = mid;
			}
			else
			{
				max = mid;
			}
		}
		if (Calc(max) >= C)
		{
			printf("%d\n", max);
		}
		else
		{
			printf("%d\n", min);
		}
	}		
	return 0;
}