2012-09-03 16:43:44Morris
[ZJ][二分Greedy] d830. 暗門2
內容 ：
在一個其大無比的空間裡，有 n 個房間相鄰著，譬如第5間的左側是第4間、右側是第6間
現在有 m 個人分別不同的房間。
但因為有些房間太空，有些則是太擠，所以我們要做一些調整，
使得每個房間裡面的人數一樣多。為了達到節能減炭的目的，
我們先假定一個k值，每個人的移動距離都不超過k，接著要求出最小的這個k
移動距離的計算方式是：某人從第i移動到第j間，則距離為 |i-j|
現在有 m 個人分別不同的房間。
但因為有些房間太空，有些則是太擠，所以我們要做一些調整，
使得每個房間裡面的人數一樣多。為了達到節能減炭的目的，
我們先假定一個k值，每個人的移動距離都不超過k，接著要求出最小的這個k
移動距離的計算方式是：某人從第i移動到第j間，則距離為 |i-j|
輸入說明
：
輸入包含多比測試資料。
第一行給定兩個整數n,m (m為n的倍數)。接著第二行有m個整數，並用空格隔開
分別表示這m個人在哪一個房間裡面。
0 <= n <= m <= 100000
輸出說明
：
輸出一個整數，代表題目敘述中所要求的k值。
範例輸入
：
4 8 1 2 3 4 2 3 4 4
範例輸出 ：
1
提示
：
出處
：
(管理：shik)
題意就不講解了, 這題的解法是 二分搜尋 k, 然後把每一個人的所在房間做一個排序,
接著當我們枚舉 k 時, 對於每一個人會產生一個可移動的區間 [ai-k, ai+k],
只要我們檢查 1~n 每個房間是不是都能包涵 m/n 個這樣的區間, 就行了。
這一個部份你可以從程式碼看出來。
那也有人會想問在檢查的時候, 會不會有問題 ?
你仔細想想, 每個區間的長度都一樣, 我先挑位於前面的區間, 不會導致後面的區間錯誤,
因為當他區間長度一樣, 就不會發生問題, 所涵蓋的區間只會多, 不會少。
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int a[100000], n, m, nm;
int test(int k) {
static int i, j, cnt;
for(i = 1, j = 0; i <= n; i++) {
cnt = 0;
while(j < m && cnt < nm && a[j]-k <= i && i <= a[j]+k) {
cnt++, j++;
}
if(cnt != nm) return 0;
}
return 1;
}
int main() {
int i;
while(scanf("%d %d", &n, &m) == 2) {
for(i = 0; i < m; i++)
scanf("%d", &a[i]);
sort(a, a+m);
nm = m/n;
int l = 0, r = n/2;
while(l < r) {
int m = (l+r)/2;
if(test(m))
r = m;
else
l = m+1;
}
printf("%d\n", r);
}
return 0;
}