倍增 + 无指定算法的排序

时间复杂度

O(N * log(N) * log(N))
运行时间: 8256 ms

Python 代码

def check(A, L, R, M, T):
    seg = A[L : R + 1]
    seg.sort()
    n = len(seg)
    if n >= 2 * M:
        upper = M
    else:
        upper = n // 2
    s = 0
    for i in range(upper):
        s += (seg[i] - seg[n - 1 - i]) ** 2
    return s <= T

def solve(A, N, M, T):
    L, R = 0, 0
    ans = 0
    while L < N:
        ans += 1
        p = 1
        while R + p < N and check(A, L, R + p, M, T):
            R += p
            p <<= 1
        p >>= 1
        while p:
            if R + p < N and check(A, L, R + p, M, T):
                R += p
            p >>= 1
        L, R = R + 1, R + 1
    print(ans)



K = int(input())
for _ in range(K):
    N, M, T = map(int, input().split())
    A = list(map(int, input().split()))
    solve(A, N, M, T)

倍增 + 归并排序

新增加的部分进行排序, 然后与原先的部分(已经排过序了)进行归并
节省了原先部分的排序计算.

时间复杂度

O(N * log(N))
运行时间: 6353 ms

Python 代码

def merge(seg_old, seg_new):
    i, j = 0, 0
    seg = []
    while i < len(seg_old) and j < len(seg_new):
        if seg_old[i] <= seg_new[j]:
            seg.append(seg_old[i])
            i += 1
        else:
            seg.append(seg_new[j])
            j += 1
    if i < len(seg_old):
        seg.extend(seg_old[i:])
    else:
        seg.extend(seg_new[j:])
    return seg


def check(seg_old, seg_new, M, T):
    seg_new.sort()
    seg = merge(seg_old, seg_new)
    n = len(seg)
    if n >= 2 * M:
        upper = M
    else:
        upper = n // 2
    s = 0
    for i in range(upper):
        s += (seg[i] - seg[n - 1 - i]) ** 2
    return s <= T, seg

def solve(A, N, M, T):
    L, R = 0, 0
    seg_old = A[L : R + 1]
    ans = 0
    while L < N:
        ans += 1
        p = 1
        while True:
            if R + p >= N: break
            seg_new = A[R + 1 : R + p + 1]
            tf, seg = check(seg_old, seg_new, M, T)
            if tf:
                R += p
                p <<= 1
                seg_old = seg
            else:
                break
        p >>= 1
        while p:
            if R + p >= N: 
                p >>= 1
                continue
            seg_new = A[R + 1 : R + p + 1]
            tf, seg = check(seg_old, seg_new, M, T)            
            if tf:
                R += p
                seg_old = seg
            p >>= 1
        L, R = R + 1, R + 1
        seg_old = A[L : R + 1]
    print(ans)



K = int(input())
for _ in range(K):
    N, M, T = map(int, input().split())
    A = list(map(int, input().split()))
    solve(A, N, M, T)