E. Hoofball

-iknoom1107

문제 설명

각 소는 가까운 소한테만 공을 패스할 수 있습니다.

N이 최대 100이라 N^2으로 풀어도 충분합니다.

1. N개의 소 중에서 한번에 가장 많은 소에게 패스할 수 있는 소를 탐색합니다.

2. 공을 패스받지 않은 소에 대해서만 1번을 반복합니다.

N마리에 소에 대해서 가장 가까운 소의 번호를 1차원 배열에 저장하면 구현할 때 더 깔끔할겁니다.

소스코드

<Python>

n = int(input())
x = [-1e9] + sorted(map(int, input().split())) + [1e9]
vst = [False] * (n + 1)
ans = 0
while True:
    tmp = []
    for i in range(1,n+1):
        if vst[i]: continue
        p = q = i
        while q <= n and x[q] - x[q - 1] > x[q + 1] - x[q] and not vst[q + 1]:
            q += 1
        while 0 < p and x[p] - x[p - 1] <= x[p + 1] - x[p] and not vst[q - 1]:
            p -= 1
        tmp.append((i - p, p, i))
        tmp.append((q - i, i, q))
    if not tmp: break
    tmp.sort()
    _, l, r = tmp[-1]
    for i in range(l, r+1):
        vst[i - 1] = True
    ans += 1
print(ans)