牛客周赛91D

题意:如果两个数的绝对差值为1，那么i和j就连了一条边，为了使得所有边可以互相到达，还需要自己加多少条边
思路:排序 + 区间划分 先从小到大排序，若a[i+1] - a[i] <= 1，则划分为同一区间，若区间内所有数相等，相当于有r-l+1个连通分量，若有任意两个值不等，那整个区间都是同一个连通分量
代码:
for _ in range(int(input())):
    n = int(input())
    a = list(map(int,input().strip().split()))
    a.sort()
    l,r = 0,0
    last = a[0]
    t = 0
    res = 0
    while r < n:
        num = a[r]
        if num - last <= 1:
            r += 1
            last = num
        else:
            if a[l] == a[r-1]:
                res += r-l-1
                t += 1
            else:
                t += 1
            l = r
            last = num
    if a[l] == a[r-1]:
        res += r-l-1
        t += 1
    else:
        t += 1
    # print(res,t)
    print(res + t - 1)