# 演算法題 - 基地台 - APCS - by Peter Wang
## 題目資訊
此題為2017.3.4 測驗中的題目4
###### tags: `APCS` `Binary Search`

## 題目敘述

### 輸入：
輸入有兩行。第一行是兩個正整數 N 與 K，以一個空白間格。第二行 N 個非負整數P[0],P[1],....,P[N-1]表示 N 個服務點的位置，這些位置彼此之間以一個空白間格。請注意，這 N 個位置並不保證相異也未經過排序。本題中，K<N 且所有座標是整數，因此，所求最小直徑必然是不小於 1 的整數。

### 輸出：
輸出最小直徑，不要有任何多餘的字或空白並以換行結尾。

## 解題思路
用Binary Search的解題想法，搜尋最大半徑。

## Binary Search 介紹
請點選此連結觀看介紹。[二分搜](https://hackmd.io/@PeterWang/HyG22BNid)

## 程式碼

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int k;
int y=1;
int arr1[50001];
bool is_cover(int x, int k){
  y = 1;
  for(int i=0;i<n;){
    while(arr1[i]+x>=arr1[y]){
      if (y == n-1) return true;
      y++;
    }
    k--;
    if(k == 0) return false;
    i=y;
  }
  return true;
}
int main(){
  while(cin>>n){
    cin>>k;
    for(int i=0;i<n;i++){
      cin>>arr1[i];
    }
    sort(arr1,arr1+n);
    int min = 1;
    int max = (arr1[n-1] - arr1[0]) / k + 1;
    while (min <= max) {
      int mid = (min + max)/2;
      if (is_cover(mid, k)){
        max = mid;
      } else {
        min = mid + 1;
      }
      if (min == max) break;
    }
    cout << min <<endl;
  }
}

## 資料來源
[zerojudge](https://zerojudge.tw/)
[題目敘述](https://zerojudge.tw/ShowProblem?problemid=c575)
[原題PDF檔](https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnx6c2dpdGl0aXR8Z3g6MTRmYzQ0ZTM0MzJjZTlhYQ)

## 備註
>[name=PeterWang]
>[time=Sun, Jun 13, 2021 11:35 PM]