提出 #77774990

ソースコード 拡げる

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
struct nuno_s {
  int L, R;
};
int cmp(const void* x, const void* y) {
  struct nuno_s a = *(const struct nuno_s*)x, b = *(const struct nuno_s*)y;
  return
    ((a.R > b.R) - (a.R < b.R)) * 2 +
    ((a.L > b.L) - (a.L < b.L));
}
int N, K;
struct nuno_s nuno[212345];
int main(void) {
  int i;
  int yes = -1, no = 1010101010;
  if (scanf("%d%d", &N, &K) != 2) return 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

struct nuno_s {
	int L, R;
};

int cmp(const void* x, const void* y) {
	struct nuno_s a = *(const struct nuno_s*)x, b = *(const struct nuno_s*)y;
	return
		((a.R > b.R) - (a.R < b.R)) * 2 +
		((a.L > b.L) - (a.L < b.L));
}

int N, K;
struct nuno_s nuno[212345];

int main(void) {
	int i;
	int yes = -1, no = 1010101010;
	if (scanf("%d%d", &N, &K) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d%d", &nuno[i].L, &nuno[i].R) != 2) return 1;
	}
	qsort(nuno, N, sizeof(*nuno), cmp);
	while (yes + 1 < no) {
		int m = yes + (no - yes) / 2;
		int cnt = 0;
		int prev = -1010101010;
		for (i = 0; i < N; i++) {
			if (prev + m <= nuno[i].L) {
				cnt++;
				prev = nuno[i].R;
			}
		}
		if (cnt >= K) yes = m; else no = m;
	}
	printf("%d\n", yes > 0 ? yes : -1);
	return 0;
}

/*

確保する距離を決め打ち → 二分探索

R の小さい順に使える布を貪欲

*/

提出情報

ジャッジ結果