C. Stable Groups Div.2

https://codeforces.com/contest/1539/problem/C
시간 1초, 메모리 256MB

input :

• n, k, x (1≤n≤200000, 0≤k≤10^18)
• a1,a2,…,an (1≤ai≤10^18)

output :

• In the only line print a single integer: the minimum number of stable groups you can split the students into.
• 최소한의 그룹의 숫자를 출력하시오.

조건 :

• A group of students is called stable, if in the sorted array of their levels no two neighboring elements differ by more than x.

• 그룹의 학생들이 안정되었다라고 하려면 정렬되어 있는 배열에서 인접한 두 원소에 대한 차이가 x보다 작아야 한다.

• teachers can invite at most k additional students with arbitrary levels (at teachers' choice)

• 추가적으로 k만큼의 학생을 추가할 수 있다. (임의로 선정이 가능)

---

우선적으로 배열을 정렬 시킨 후에 입력된 배열 자체만으로 안정된 그룹을 만드려면 몇 명이나 더 필요한지를 구하자. 그리고 이 인원(cnt라고 부르도록 하겠다) k보다 크다면 조건을 만족시키지 못하므로 그룹을 더 나누어야 한다.

그룹을 나누게 된다면 추가된 인원이 없어도 되니까 cnt에서 값을 빼주어야 한다. 그리고 이 값을 k와 비교하면서 k보다 작거나 같아지는 경우를 찾아 주고 이 때의 그룹의 수가 정답이 된다.

맨 처음에 이 추가하는 인원을 우선순위 큐를 이용해서 작성하였더니 시간 복잡도에 문제가 발생하였다. 리스트를 이용해서 인원이 많이 드는 부분(리스트의 정렬을 한 후 가장 뒤에서 부터)에서 부터 제거하는 방식을 사용하니 시간 복잡도를 만족시켰다.

가장 뒤에서 부터 마지막 완료된 지점까지의 차이가 그룹의 개수를 나타낸다고 볼 수 있다.
인원을 추가할 때마다 그룹이 하나씩 늘어나기 때문에 그렇다고 할 수 있다.

import sys

n, k, x = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
temp = []
data.sort()

cnt = 0
for i in range(1, len(data)):
    term = (data[i] - data[i - 1] - 1) // x
    if term > 0:
        temp.append(term)
        cnt += term

temp.sort()
idx = len(temp) - 1
while cnt > k:
    cnt -= temp[idx]
    idx -= 1

print(len(temp) - idx)