레이팅 미적용설명
농부 존의 농장을 가로지르는 긴 도로에는 \(N\)개의 횡단보도가 있으며, 편의상 \(1 \ldots N\)번으로 번호가 매겨져 있다 (\(1 \leq N \leq 100,000\)). 소들이 이 횡단보도에서 길을 건널 수 있도록 FJ는 전자 횡단 신호기를 설치했는데, 소가 건너도 될 때는 초록색 소 아이콘이 켜지고 그렇지 않을 때는 빨간색이 켜진다. 안타깝게도 큰 뇌우로 인해 일부 신호기가 고장 났다. 고장 난 신호기의 목록이 주어질 때, 적어도 \(K\)개의 작동하는 신호기가 연속으로 이어진 구간이 존재하도록 하기 위해 FJ가 수리해야 하는 신호기의 최소 개수를 계산하시오.
문제 출처: Brian Dean
제약
문제 출처: Brian Dean
입력 형식
입력의 첫째 줄에 \(N\), \(K\), \(B\)가 주어진다 (\(1 \leq B, K \leq N\)). 다음 \(B\)개의 줄에 고장 난 신호기의 ID 번호가 하나씩 주어진다.
출력 형식
도로 어딘가에 \(K\)개의 작동하는 신호기가 연속으로 이어진 구간이 존재하도록 하기 위해 수리해야 하는 신호기의 최소 개수를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
maxcross.in · 출력을 쓸 파일 maxcross.out예제 1
입력
10 6 5
2
10
1
5
9출력
1문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2016-2017 > February > Silver
태그