Haidora və borular (Həll təhlili)

Həll

Boruları sıralamaq optimaldır, çünki bu, maksimum blok sayını effektiv şəkildə əldə etməyə imkan verir, biz \mathcal{O}(n\log n) (və ya hətta əl ilə yazılmış, yəni \mathcal{O}(n^2) işləyən Bubble sort) olan daxili bir birləşdirmə sıralama funksiyasını istifadə edə bilərik, və bundan sonra sıralanmış massivdə iterasiya edərək birləşdirə biləcəyimiz maksimum boru sayını hesablayırıq və əgər daha artıq uzadıla bilməzsə, onun uzunluğunu blok ölçüləri $S$ massivinə saxlayırıq, və cavab sonunda \max_{1 \le i \le |S|} S_i olacaq.

Komplekslik \mathcal{O}(n^2) və ya \mathcal{O}(n \log n) olacaq, tətbiqdən asılı olaraq.

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()