https://www.acmicpc.net/problem/24913
문제 요약
- 투표 결과를 확인 중. 두 가지 쿼리를 해결
- 특정 후보에게 표 + x, 정후가 당선 가능한지 쿼리
- 최고 득표가 같으면 당선 아님
접근법
- 조건을 놓치거나, 구현이 이상하면 틀림
- 이상적인 상황 즉, 나머지 후보들에게 가는 표가 잘 분배되었을때를 고려하여 접근
- 조건 1 : 최고 득표 >= 정후 득표
- 정후가 득표를 해도 최고 득표자를 못 넘으면 실패
- 조건 2 : 잘 분배 했을때 최고 득표 >= 정후 득표
- 잘 분배가 되어서 어쩔 수 없이 최고 득표가 생길텐데, 그래도 정후가 못 넘으면 실패
- 표를 공평하게 나눠 갖는 다면 : (기존에 다른 후보가 얻은 득표 + 추가로 얻은 득표) / n
- 에누리가 생기면 + 1 ==> 이때가 공평하게 나눴을 때 최고 득표가 됨
newbieski