基地台

#include <iostream>
using namespace std;
int n, k, v[50001];
void sort();
bool test(int);
int main(){
	int min, max, mid;
	cout<<"請輸入服務數n, 基地台數 k :";
	scanf("%d %d", &n, &k);
	v[0]=1;v[1]=2;v[2]=5;v[3]=7;v[4]=8;
/*
	cout<<"請輸入位址 : ";
	for (int i=0;i<n;i++){
		scanf("%d", &v[i]);
	}
	for (int i=0;i<n;i++){
		printf("%d ", v[i]);
	}
	printf("\n");
	*/
	sort();
	min=1;
	max=(v[n-1]-v[0])/k+1;
	while(min<max){//二分法
		mid=(min+max)/2;
		if(test(mid))max=mid;//有含蓋, 再縮小看看
		else min=mid+1;//沒含蓋, 放大看看
	}
	printf("最大直徑 : %d",max);
}
bool test(int x){//計算是否有在含蓋範圍內
	int next, count=0;
	for(int i=0;i<n;){ next=v[i]+x;//蓋下一個基地台的含蓋範圍 count++;//建立一座基地台 if(count>k)return false;//超出最大的基地台了
		if(v[n-1]<=next && count<=k)return true;//最後一個基地台, 有含蓋最後一個服務站
		do{
			i++;
		}while(v[i]<=next);
	}
	return false;
}
void sort(){
	for (int i=0;i<=n-2;i++){
		for (int j=i+1;j<=n-1;j++){ if(v[i]>v[j]){
				int tmp=v[i];
				v[i]=v[j];
				v[j]=tmp;
			}
		}
	}
}