2456.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 46 行

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

int pos[100000], n, cc;

bool check( int l )
{
	int i, r, j;
	for( r=cc-1,i=0,j=1; j<n && r; j++ )
	{
		if( pos[j]-pos[i]>=l )
		{
			r--;
			i=j;
		}
	}
	return r == 0;
}

int main()
{
	int i, j, a, b, c;
	scanf( "%d %d", &n, &cc );

	for( i=0; i<n; i++ )
	scanf( "%d", &pos[i] );

	sort( pos, pos+n );	

	a = 0, b = ( pos[n-1] - pos[0] ) / ( cc - 1 ) + 1;
	
	while( b > a+1 )
	{
		c = ( a + b ) / 2;
		if( check(c) ) a = c;
		else b = c;
	}
	printf( "%d\n", a );

	return 0;
}