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

1527： ◆adhRKFl5jU：2009/03/01(日) 18:34:44: jid28
問題番号 10
点数 30
-----
// O(M^3)

#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 ans = 1000000000;

for (int k = 0; k <= 1; k++) {
for (int i = 0; i < M; i++) {
for (int j = i; j < M; j++) {
int d = X[k][j] - X[k][i];
if (greedy(0, d) + greedy(1, d) <= N) ans = min(ans, d);
}
}
}

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

return 0;
}

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

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

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

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