레이팅 미적용농장의 무더운 여름날, 농부 존이 \(N\)마리의 소들에게 레모네이드를 나눠 주고 있다! \(N\)마리의 소들(편의상 \(1 \dots N\)으로 번호가 매겨져 있다)은 모두 레모네이드를 좋아하지만, 그중에는 유독 더 좋아하는 소들도 있다. 구체적으로, 소 \(i\)는 레모네이드를 받기 위해 최대 \(w_i\)마리의 소 뒤에 줄을 서서 기다릴 의향이 있다. 지금은 \(N\)마리의 소가 모두 들판에 있지만, 농부 존이 워낭을 울리는 순간 소들은 즉시 농부 존의 레모네이드 가판대로 몰려올 것이다. 소들은 모두 농부 존이 레모네이드를 나눠 주기 시작하기 전에 도착하지만, 어떤 두 소도 동시에 도착하지는 않는다. 또한 소 \(i\)는 도착했을 때 이미 줄에 서 있는 소가 \(w_i\)마리 이하일 때, 그리고 그때에만 줄에 선다.
농부 존은 레모네이드를 미리 어느 정도 준비해 두고 싶지만, 낭비하고 싶지는 않다. 줄에 서는 소의 수는 소들이 도착하는 순서에 따라 달라질 수 있다. 줄에 서는 소의 수의 최솟값을 구하도록 도와주자.
출제자: Dhruv Rohatgi
출제자: Dhruv Rohatgi
첫째 줄에 \(N\)이 주어지고, 둘째 줄에 공백으로 구분된 정수 \(N\)개 \(w_1, w_2, \dots, w_N\)이 주어진다. \(1 \leq N \leq 10^5\)이고, 각 소 \(i\)에 대해 \(0 \leq w_i \leq 10^9\)임이 보장된다.
소들이 도착할 수 있는 모든 순서 가운데, 줄에 서게 될 수 있는 소의 수의 최솟값을 출력한다.
lemonade.in · 출력을 쓸 파일 lemonade.out5
7 1 400 2 23In this setting, only three cows might end up in line (and this is the smallest
possible). Suppose the cows with \(w = 7\) and \(w = 400\) arrive first and wait in
line. Then the cow with \(w = 1\) arrives and turns away, since 2 cows are already
in line. The cows with \(w = 2\) then arrive, one staying and one turning away.
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > US Open > Silver