#include "stdio.h"
#include "memory.h"
long  n,c;
long  a[100001];


long partition(long low,long high)
{
	long temp;
	temp=a[low];
	while(low<high){
		while(low<high&&a[high]>=temp) --high;
		a[low]=a[high];
		while(low<high&&a[low]<=temp) ++low;
        a[high]=a[low];
	}
	a[low]=temp;
	return low;
}

long quick(long low,long high)
{
	long pivotloc;
	if(low<high) {
		pivotloc=partition(low,high);
		quick(low,pivotloc-1);
		quick(pivotloc+1,high);
	}
	return 1;
}

void bisection(long min,long max)
{
	long medi,i,num,temp1,flag;
	long high,low;
	low=1;
	high=max-min+1;
    while(high-low>1)
	{
		num=c;
		medi=(low+high)/2;
		temp1=a[1]; 
		flag=0;
		num--;
		for(i=2;i<=n;i++)
		{
			if(a[i]-temp1>=medi)
			{
				num--;
				temp1=a[i];
				if(num==0)
				{
					flag=1;
					break;
				}
			}
		}
	    if(flag==1) low=medi;
		    else
			   high=medi;
	}
	    printf("%ld\n",low);
}

long  main()
{
	long i,max=0,min=1000000001;
	scanf("%ld%ld",&n,&c);
	memset(a,0,sizeof(a));
	for(i=1;i<=n;i++)
	{
		scanf("%ld",&a[i]);
		if(a[i]<min) min=a[i];
                  if(a[i]>max) max=a[i];
	}
	quick(1,n);
	bisection(min,max);
	return 1;
}

• 先对给定的位置从小到大排序,然后用折半(二分)来 确定largest minimal distance!! 超时啊!! (1383) ook 2005-07-26 19:24:10
  • 这样可以剩时间. (108) tq 2005-08-07 20:46:58