Codeforce #521 Div3 E. Thematic Contests

문제 원본

---

문제 설명

문제 토픽 N개 가 입력으로 주어 진다.

하루에 하나의 콘테스트가 열리는데 같은 토픽 k개를 제출 할 수 있고 해당 콘테스트는 이전에 열린 콘테스트보다 정확히 2배 많은 토픽을 출제 해야 한다.

이때 최대로 낼 수 있는 문제를 구하는 문제

EX)

첫 번째 input data

18

2 1 2 10 2 10 10 2 2 1 10 10 10 1 1 10 10

첫 째날 1토픽 2개 둘 째날 2토픽 4개 셋 째날 10토픽 8개 총 14개의 문제를 출제 할 수 있다.

---

문제 풀이

1 step

    입력 받은 원소를 정렬한다.

2 step

    정렬된 입력받은 원소를 가지고 이분 탐색을 이용하면 각 원소의 개수를 구할 수 있다.

    위 예에서 원소를 정렬 하면

    1 1 1 1 2 2 2 2 2 10 10 10 10 10 10 10 10 10 이된다.

    이분 탐색으로 1의 시작인덱스와 1의 끝 인덱스를 구하면 해당 원소의 개수가 된다.

    1 : 4개

    2 : 5개

    10 : 9개

    원소의 개수를 배열에 저장 한 후 원소의 개수를 정렬 한다.

    정렬된 원소개수 배열 [4,5,9]

    

3 step

    정렬된 원소의를 이용해 모든 상황을 시뮬레이션 한다.

    첫 번째 콘테스트의 문제 개 수를 선택 할 수 있는 경우는 1 ~  원소의 최대 개수가 될 수 있다.

    위 예에서 보면 1 ~ 9 이다.

    첫 번째 루프에서 첫 번째 콘테스트에서 출제 할 문제수를 정한뒤 탐색할 정렬된 원소 개수 배열의 인덱스를 구한다.

    만약 예제에서 첫 번째 콘테스트에서 5개의 문제를 출제 해야 한다면 첫 번째 개수인 4는 탐색할 필요가 없기 때문에 가능한 원소 부터 탐색한다.

    탐색할 인덱스를 구하면 조건에 맞게 시뮬레이션을 한다.

---

소스코드