UVA – 11516 – WiFi   Leave a comment


Binary search the answer, a good note is that the minimum distance is always on the form x.0 or x.5 nothing else.

#include <stdio.h>
int loc[100005];
int compare(const void *a,const void *b)
{
	int* ia = (int*)a;
	int* ib = (int*)b;
	return ((*ia)<(*ib)) ? -1 : 1;
}
int main()
{
	int tc;
	scanf("%d",&tc);
	while(tc-->0)
	{
		int s,h,i,j,lo,hi,mid;
		scanf("%d %d",&s,&h);	
		for(i=0;i<h;i++)
			scanf("%d",loc+i);
		qsort(loc,h,sizeof(int),compare);
		lo = 0;
		hi = 2*(loc[h-1]-loc[0]+1);
		while(hi>lo)
		{
			mid = (lo+hi)/2;
			int start = loc[0];
			int needed = 1;
			for(i = 1;i<h;i++)
				if(loc[i]>start+mid)
				{
					start = loc[i];
					needed++;
				}
			if(needed>s)
				lo = mid+1;
			else
				hi = mid;
		}
		printf("%.1f\n",hi/2.00);
	}
	return 0;
}

Advertisements

Posted June 24, 2012 by epicrado in Binary search

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: