2485646_ac_77ms_512k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 45 行

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

int a[100001];
int n, c;

int main()
{
	int i, j, no;
	int min, max, mid;

	scanf("%d%d",&n,&c);
	for(i = 0; i < n; i++)
		scanf("%d",&a[i]);
	sort(a,a+n);
	min = a[0],max = a[n-1];
	while(min<max)
	{
		mid = (min+max)/2;
		no = 0;
		for(i = 0; i < n; i++)
		{
			j = i;
			while(j<n&&a[j]<a[i]+mid)
				j++;
			if(j!=n)
				no++;
			if(no>c)
				break;
			i = j-1;
		}
		no++;
		if(no<c)
			max = mid;
		else
		{
			if(min==mid)
				break;
			min = mid+(min==mid);
		}
	}
	printf("%d\n",min);
	return 1;
}