USACO 2020 Open Contest Silver #1(Credit: Brian Dean)- 사회적 거리두기 3 > 문제은행 : 정보올림피아드&알고리즘




3687 : 사회적 거리두기 3

제한시간
2000 ms   
메모리제한
256 MB   
해결횟수
3 회   
시도횟수
21 회   

문제

농부 창호는 요즈음 대유행중인 무서운 소로나 바이러스(COWVID-19) 때문에
고민이 많다.



 

농부 창호는 소들의 오후 일과를 위해, 일직선 좌표계로 표현되는 목장에
N마리의 소들을 배치시키려고 한다

목장 내에는 [s,e]로 표현되는 M개의 구간이 있으며, 이 구간 내에 있는 풀은 잘 자라서 먹을 수 있다

 

농부 창호는
모든 소들을 이 구간 내에 배치시키되, 사회적 거리두기를 위해 소들간의 거리를 최대화시키고자 한다

 

구체적으로는, 두 소 사이의 거리의 최솟값이 D라고 하면, D를 최대화시키려고 한다

D를 구하는 프로그램을 작성하라. (소들은 무조건 정수 좌표 위에 배치되며, 구간 [s,e]에서 각 경계 좌표인 s
e
에도 소들이 위치할 수 있다.) 


입력형식

첫 줄에 정수 N M이 주어진다. (2≤N≤​100,000, 1≤​M≤​100,000)

다음 M줄에 걸쳐서, 소들이 먹을 수 있는 풀이 있는 구간인 s e가 공백을 사이에 두고 주어진다.

각 좌표는 1이상 10​18이하의 정수이다.

그 어떤 두 구간도 겹치거나 맞닿지 않는다.


출력형식

D의 최댓값을 첫 줄에 출력한다. D>0인 답이 나올 수 있는 입력예시가 항상 보장된다.


입력 예

5 3
0 2
4 7
9 9

출력 예

2

Hint!

D=2를 만족시키는 한 가지 방법은 소들을 각각 x = 0, 2, 4, 6, 9에 배치하는 것이다.





이진 탐색, 파라메트릭 서치

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP