Гайдо́ра та труби (Розбір)

Рішення

Оптимально відсортувати труби, оскільки це дозволяє нам ефективно отримати максимальну кількість блоків, ми можемо використовувати вбудовану функцію злиття, яка працює за \mathcal{O}(n\log n) (або навіть написану вручну, тобто сортировку бульбашкою, яка працює за \mathcal{O}(n^2)), а після цього ми обчислюємо максимальну кількість труб, які можемо з'єднати, перебираючи відсортований масив і накопичуючи блок, якщо його більше не можна розширити, ми зберігаємо його довжину в масиві розмірів блоків $S$, а відповідь врешті-решт буде \max_{1 \le i \le |S|} S_i.

Складність буде \mathcal{O}(n^2) або \mathcal{O}(n \log n) в залежності від реалізації.

def solve():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    cur=1
    S=[]
    for i in range(n-1):
        if(a[i+1]-a[i]<2):
            cur+=1
        else:
            S.append(cur)
            cur=1
    S.append(cur)
    print(max(S))

for _ in range(int(input())):
    solve()