레이팅 미적용소 베시는 컴퓨터 과학에 대한 사랑, 그리고 언젠가 "베시 박사"가 될 수 있다는 매력에 이끌려 컴퓨터 과학 박사 과정에 입학했다. 얼마간 학술 연구를 해 온 베시는 지금까지 논문을 \(N\)편(\(1 \leq N \leq 10^5\)) 발표했고, \(i\)번째 논문은 학계의 다른 논문들로부터 \(c_i\)번(\(0 \leq c_i \leq 10^5\)) 인용되었다.
베시는 학자의 성공을 \(h\)-지수로 측정할 수 있다는 이야기를 들었다. \(h\)-지수란, 연구자가 각각 \(h\)회 이상 인용된 논문을 \(h\)편 이상 가지는 가장 큰 수 \(h\)이다. 예를 들어 논문이 \(4\)편이고 각 인용 횟수가 \((1,100,2,3)\)인 연구자의 \(h\)-지수는 \(2\)이지만, 인용 횟수가 \((1,100,3,3)\)이라면 \(h\)-지수는 \(3\)이 된다.
\(h\)-지수를 올리기 위해, 베시는 자신의 과거 논문 여러 편을 인용하는 서베이 논문을 쓸 계획이다. 페이지 제한 때문에 이 서베이에는 인용을 최대 \(L\)개(\(0 \leq L \leq 10^5\))까지만 포함할 수 있으며, 물론 각 논문은 최대 한 번만 인용할 수 있다.
이 서베이를 쓴 뒤 베시가 달성할 수 있는 최대 \(h\)-지수를 구하는 것을 도와주자.
참고로, 베시의 지도교수는 언젠가 \(h\)-지수를 올리기 위한 목적만으로 서베이를 쓰는 것은 윤리적으로 의심스러운 행위라고 알려 주어야 할 것이다; 다른 학자들은 여기서 베시를 따라 하지 않기를 권한다.
문제 제공: Dhruv Rohatgi
채점 방식
- 테스트 케이스 1-7은 \(N \leq 100\)을 만족한다.
- 테스트 케이스 8-10은 \(N \leq 1000\)을 만족한다.
- 테스트 케이스 11-17은 \(N \leq 10^5\)를 만족한다.
문제 제공: Dhruv Rohatgi
입력의 첫째 줄에 \(N\)과 \(L\)이 주어진다.
둘째 줄에 공백으로 구분된 \(N\)개의 정수 \(c_1,\ldots, c_N\)이 주어진다.
서베이를 쓴 뒤 베시가 달성할 수 있는 최대 \(h\)-지수를 출력한다.
4 0
1 100 2 32Bessie cannot cite any of her past papers. As mentioned above, the \(h\)-index for
\((1,100,2,3)\) is \(2\).
4 1
1 100 2 33If Bessie cites her third paper, then the citation counts become \((1,100,3,3)\).
As mentioned above, the \(h\)-index for these counts is \(3\).
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > US Open > Bronze