二分 + 区间合并

python 代码

T = int(input())
def check(mid,n):
    area = []
    st = -1
    ed = -1
    for i in range(k):
        left = max(1,a[i] - (mid - 1))
        right = min(n,a[i] + (mid - 1))
        area.append([left,right])
    area.sort()
    for i in range(k):
        if ed + 1 < area[i][0]:
            st = area[i][0]
            ed = area[i][1]
        else:
            ed = max(ed,area[i][1])
    if st == 1 and ed == n:
        return True
    else:
        return False
while T:
    T = T - 1
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    l,r = 1,n
    while l < r:
        mid = (l + r) // 2
        if check(mid,n):
            r = mid
        else:
            l = mid + 1
    print(r)