BOJ 17449 - 순위 계산
최대 등수는 쉽다. 현재 등수가 $c$ 라면 $a_i \le c$ 라면 $1$씩 더해주기만 하면 된다.
최소 등수는 그리디하게 생각하고, 현재 자신과 같은 등수의 사람 수를 계속 관리한다.
현재 자기 등수가 $c$이고 같은 등수 사람이 $d$명일 때 $c+d>a_i$ 라고 하면 $d$명의 사람이 모두 $c$라는 것에 모순이므로 $a_i-c$ 명은 $c \sim a_i-1$ 등에 각각 한 명씩 배분이 되게 해주고 $d \coloneqq d - (a_i-c)+1$ 를 처리해주고 자신의 등수를 $c$ 로 바꿔주면 된다.
Comments