هايدورا والأنابيب (شرح الحلول)

الحل

من الأمثل فرز الأنابيب، حيث يسمح لنا ذلك بكفاءة بالحصول على الحد الأقصى لعدد الكتل، يمكننا استخدام دالة الفرز المدمجة التي تعمل في \mathcal{O}(n\log n) (أو حتى واحدة مكتوبة يدويًا مثل خوارزمية Bubble Sort التي تعمل في \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()