Codeforces Round #792 (Div. 1 + Div. 2) E. MEX vs DIFF

Problem - E - Codeforces

간단한 문제지만 업솔빙에 시간이 좀 걸려서 정리.

최소의 비용을 찾기 위해선 d(a)가 작아져야하고 m(a)가 커져야 한다.

잘 생각해 보면 m은 d보다 커질 수 없다.

m이 커지려면 0부터 m-1까지의 숫자가 배열 a에 존재해야 한다.0부터 m-1까지의 숫자가 존재하면 d는 m이 되어버리기 때문이다.

반대로 d는 m보다 커질 수 있다.

m보다 큰 숫자가 존재하면 d의 값이 1이 증가하기 때문이다.

결국 문제를 요약하자면, 배열 a에서 m값보다 큰 숫자 종류의 개수가 문제에서 정의하는 비용이다.

m값보다 큰 숫자 종류를 줄이기 위해서는 m값을 크게 키우면 된다.

이는 배열 a의 어떠한 값을 m으로 바꿔 준다면 m값은 1이 증가하게 된다.

이러한 연산을 최대 k개 사용할 수 있으로 최대 k개를 사용하고 난 후의 m값을 찾는다.

그 m값보다 큰 값중에서 사용한 연산의 수만큼 제거해주면 된다.

d값을 줄이기 위해서는 적게 겹치는 값을 사용하면 빠르게 d가 줄어들기 때문에 m값보다 큰 값중에서 적게 겹치는 값을 사용해주면 된다.

이는 우선순위 큐로 구현할 수 있다.

만약 m값보다 큰 값이 더 이상 존재하지 않게 된다면그냥 m값내에 중복된 값을 사용해서 채워주면 되기 때문에 문제가 되지 않는다.

따라서 정답은 우선순위 큐에 존재하는 값의 개수로 도출할 수 있다.