Xây dựng mảng phần tử riêng biệt với kích thước, tổng và giới hạn trên cho trước trong Python

Cho kích thước N, tổng SUM, giới hạn trên K (không phần tử nào > K). Tìm mảng các phần tử riêng biệt thỏa mãn. Trả về -1 nếu không có lời giải.

Ví dụ: N=4, SUM=16, K=9 → [1,2,4,9].

Thuật toán

• minimum_sum = N*(N+1)/2
• maximum_sum = N*K - N*(N-1)/2
• Nếu SUM ngoài khoảng → -1
• Khởi tạo res = [0,1,2,...,N], sum = minimum_sum
• Từ i=N xuống 1: cố gắng tăng res[i] lên K cho đến khi đạt SUM

Ví dụ mã Python

def get_arr(N, SUM, K):
    minimum_sum = (N * (N + 1)) / 2
    maximum_sum = (N * K) - (N * (N - 1)) / 2
    if minimum_sum > SUM or maximum_sum < SUM:
        return -1
    res = [i for i in range(N + 1)]
    sum = minimum_sum
    i = N
    while i >= 1:
        x = sum + (K - i)
        if x < SUM:
            sum = sum + (K - i)
            res[i] = K
            K -= 1
        else:
            res[i] += (SUM - sum)
            sum = SUM
            break
        i -= 1
    return res

N = 4
SUM = 16
K = 9
print(get_arr(N, SUM, K))

Đầu vào

4, 16, 9

Đầu ra

[0, 1, 2, 4.0, 9]