> #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;
> }

• 这样可以剩时间. (108) tq 2005-08-07 20:46:58