====== Array Cloning Technique ======

  * 처음 주어진 배열의 원소들 중에서, 가장 빈도수가 높은 원소로 다른 모든 원소들을 바꿔주는게 최선이다.
  * 가장 빈도수가 높은 원소가 x, 그 빈도수가 k라고 하면, 필요한 연산의 횟수는 시뮬레이션으로 구할수 있다. 수열을 클론하고 -> 클론한 수열의 모든 x를 스왑해서 빈도수를 2k로 만들고 -> 다시 그 수열을 클론하고 -> 2k번 스왑해서 빈도수를 4k로 만들고 -> ... 이것을 반복하면 된다. 시간복잡도는 O(logn) 이다.
  * 문제 자체는 간단한데, 처음 원소들 중에서 가장 빈도수가 높은 원소를 구하는 부분에서 주의가 필요하다.
    * 딕셔너리 기반의 자료구조를 이용해서 계산하면, [[ps:tutorial:hash table hack]]에 의해 TLE가 난다. 그것을 피하기 위해서 여기에서는 수열을 정렬한 뒤 순서대로 읽으면서 각각 원소의 빈도수를 세었다.
    * 특히 이 문제는 [[ps:tutorial:hash table hack]]에서 [[ps:tutorial:hash table hack#실제 예]]로 사용한 문제이다. 이 부분 구현 방법에 대한 분석은 링크 참고.

===== 코드 =====
{{gh>https://github.com/teferi00/problem_solving/blob/main/problems/codeforces/q1665b.py}}


{{tag>codeforces}}