管理人の独り言（プログラミング関連）

1525： ◆adhRKFl5jU：2009/03/01(日) 18:33:13: jid26
問題番号 10
点数 100
-----
// O(M logW)
// W は座標の値の差の最大値

#include <cstdio>
#include <algorithm>
using namespace std;

int N, M, X[2][100010];

int greedy(int k, int d) {
int prv = X[k][0], cnt = 1;
for (int i = 1; i < M; i++) {
if (X[k][i] <= prv + d) continue;
prv = X[k][i];
cnt++;
}
return cnt;
}

int main() {
scanf("%d%d", &N, &M);
for (int i = 0; i < M; i++) scanf("%d%d", &X[0][i], &X[1][i]);

sort(&X[0][0], &X[0][M]);
sort(&X[1][0], &X[1][M]);

int lo = -1, up = 1000000000;
while (up - lo > 1) {
int mid = (lo + up) / 2;
if (greedy(0, mid) + greedy(1, mid) <= N) up = mid;
else lo = mid;
}

printf("%d\n", up);

return 0;
}

※書き込む際の注意事項はこちら

※画像アップローダーはこちら

（画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります）

掲示板管理者へ連絡無料レンタル掲示板