作者：feintKotlin

題目來源：hackerrank

關鍵字：演算法；kotlin；流程圖；程序；

演算法挑戰第四天，難度中等

題目

Hackerland是一個一維的城市，擁有n棟房子，其中房子i 位於x軸的x_i位置。Mayor想要在城市中的房子屋頂上安裝無線電發射機。每個發射機都有一個範圍，k，意味著它可以將信號發射到所有距離在k個單位內（<=k）的房子。

給定一張Hackerland的地圖和k的值，你能找到覆蓋城市中所有的房子所需要的最小的信號發射器的數量嗎？（每個房子至少得被一個發射器覆蓋）。每個發射器都必須安裝在已經存在的房子的頂部。

輸入格式

第一行包含兩個用空格分隔的整數，分別表示n的值（Hackerland中房子的數量）和k的值（每個發射器所能覆蓋的範圍）。

第二行包含n個使用空格分隔的整數，表示各個房子所在的位置（x_1,x_2,...,x_n）

約束條件

• 1<=n,k<=10^5

• 1<=x_i<=10^5

輸出格式

列印單個整數，表示覆蓋城市中所有的房子所需要的最小的信號發射器的數量。

實例輸入0

5 1

1 2 3 4 5

實例輸出0

2

實例解析0

下圖為Hackerland的地圖

地圖

當我們把發射器安裝道2和4的時候能夠覆蓋道整個城市，所以我們在新的一行中列印出2。

(以上為題目的相關內容，大家可以先自己思考一翻，然後在瀏覽下方的解題過程)

解析

這道題倒是挺符合它著中等難度的。想了好一會才弄出來了。我採取的解決方案，邏輯稍微有點複雜，使用文字不太好表述。所以咱就畫一些圖，來變現下我這演算法的過程吧。

示意圖1

示意圖2

我們只需要重複以上步驟，直到A1,A2,...,An的元素數量之和等於房子的數量為止。然後圖左側的那個列表中所剩的元素的個數，即為覆蓋整個城市所需要的最少的發射器個數。

流程圖

(由於代碼邏輯較為複雜，我就挑選幾個比較重要的部分來畫)

獲取當前位置，發射器所能覆蓋的房屋

對應示意圖中的操作

代碼

代碼1

代碼2

結語：哎，真不知道hackerrank對於超時的具體定義。有一個測試用例，裡面有8萬個房子的位置，我試著在IDEA跑了下也就3秒左右的時間。可hackerank還是顯示超時了，難道必須要在1秒內完成嗎。。。想哭。只能說現在使用的這個方法的時間複雜度還是太高。如果你有更好的方法的話，就在評論里說一說唄。