Cellular Network [Codeforces 教育15 : C]

問題

http://codeforces.com/contest/702/problem/C

直線上にn個の街とm個の基地局がある。
基地局が全ての街をカバーするための基地局の最小の半径rは？

1 <= n,m <= 10^5
各座標 [-10^9, 10^9]

考察

1. 街・基地局はソートができるのでする
2. ある街は最低1つの基地局が必要
3. 全ての街に対して最も近い基地局への距離を求めて、その最大値が答え
4. 愚直にやると O(nm) でダメ

5. 高速化するために基地局をソートする
6. 今知りたいのは、ある街の座標について、その街の座標より小さくて最大の座標と、大きくて最小の座標
7. upper_bound, lower_boundあたりを使えばできる
8. 中身で二分探索してるので、これを使えばO(log m)で各クエリ最も近い基地局への距離が求まる
9. これでO(n log m)となり、いける

実装

http://codeforces.com/contest/702/submission/19521338

#define INF INT_MAX/2
//-----------------------------------------------------------------
int n, m;
int a[101010], b[101010];
//-----------------------------------------------------------------
int main() {
	cin >> n >> m;
	rep(i, 0, n) scanf("%d", &a[i]);
	rep(i, 0, m) scanf("%d", &b[i]);
	b[m] = INF;
	b[m + 1] = -INF;
	m += 2;
	sort(b, b + m);

	int ans = 0;
	rep(i, 0, n) {
		int idx = lower_bound(b, b + m, a[i]) - b;
		
		int l = b[idx - 1];
		int r = b[idx];

		if (l == -INF)
			ans = max(ans, r - a[i]);
		else if (r == INF)
			ans = max(ans, a[i] - l);
		else
			ans = max(ans, min(r - a[i], a[i] - l));
	}
	cout << ans << endl;
}