b252:
加建
Content
有一個城市, 其內有一條長長的主路。這條路分成 M段等距的路區,
這些路區上有些是一個休閒區，有些是房屋區。其中, 第一個房屋區是在第 1 個路區上，
而最後一個路區則在第 M 個路區上。M亦是最後一個路區。 (M<= 1,000,000)
當地政府希望增加些房屋區的數量，於是希望將其中一部分原為休閒區的路區改建為房屋區。
因考慮到環保因素, 政府希望在選擇新房屋區時，會保證新選擇的新房屋區的兩側，
距離其他原有或將會有的建房屋區的之間必定保留有最少 K 個休閒區。
現在給定原本房屋區所在路區的編號，求要在合乎上述條件下，最多可新增多少個房屋區?
要注意的是留有 K 段休閒區的要求，只是對新建房屋而言，原有房屋區之間]的距離，可能未必合乎這個要求。
另外，所選擇的路區，必定是在該條主路上的。
換言之，所選用以改建的路區編號，必須在 1 至M 之間，並且原本是一個休閒路區。
Input
輸入中有若干組測試數據，每組測試數據的格式如下:
-
每組測試數據的第一行上有兩個正整數 N, 及 K。其中，N 代表有多少個現存的房屋區，而 K 的意思可參閱上面內文說明。( 2<= N <= 50)
-
隨後的一行上有 N 個整數, 每個整數之間以一個空格分開。第一個整數必定是 1，最後一個就是 M。並且這些編號在輸入資料中是由小至大排列好。這些數字代表著原本為房屋區的區號。
輸入的最後一行只有兩個 0, 代表數據的結束。
Output
對應於每一組輸入的測試數據,，請輸出一個非負整數，它代表最多可選擇成為新增的房屋區的數目。
Sample Input
#1
4 2 1 3 5 6 5 2 1 4 13 19 21 0 0
Sample Output
#1
0 3
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (1%): 1.0s , <1K
不公開 測資點#1 (9%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1K
不公開 測資點#6 (10%): 1.0s , <1K
不公開 測資點#7 (10%): 1.0s , <1K
不公開 測資點#8 (10%): 1.0s , <1K
不公開 測資點#9 (10%): 1.0s , <1M
不公開 測資點#10 (10%): 1.0s , <1M
不公開 測資點#0 (1%): 1.0s , <1K
不公開 測資點#1 (9%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1K
不公開 測資點#6 (10%): 1.0s , <1K
不公開 測資點#7 (10%): 1.0s , <1K
不公開 測資點#8 (10%): 1.0s , <1K
不公開 測資點#9 (10%): 1.0s , <1M
不公開 測資點#10 (10%): 1.0s , <1M
Hint ：
注:
- 在第一個測試數據中，不能找到任何可以轉變為房屋區的路區。
- 在第二個測試數據中，在 4 和 13 之間，可以新增 2 個房屋區；而在 13 和 19 之間，以新增 1 個房屋區。因此共可以新增 3 個房區。
Tags:
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||