第三题可以二分写的，对K值二分，最大的合法K值就是答案：

import sys
if __name__ == "__main__":
        t = int(sys.stdin.readline().strip())
        while t > 0:
            t -= 1
            line = sys.stdin.readline().strip().split(' ')
            n, m = int(line[0]), int(line[1])
            hs = [int(c) for c in line[2:]]
            hs = sorted(hs)
            l, r = 0, max(hs)
            def check(mid, m):
                cur_h = -float('inf')
                count = 0
                for h in hs:
                    if cur_h+mid <= h:
                        count += 1
                        cur_h = h
                if count < m:
                    return False
                else:
                    return True

            while l<=r:
                mid = (l+r)/2
                if check(mid, m):
                    l = mid+1
                else:
                    r = mid-1
            print r