Chương trình tìm lợi nhuận tối đa bán bóng giảm giá theo màu trong Python

Mảng inventory[i] = số bóng màu i. Khách đặt orders bóng. Giá bóng màu = số lượng còn lại của màu đó (bán 1 → giá giảm 1). Tìm tổng giá trị lớn nhất, modulo 10⁹+7.

Ví dụ: inventory=[5,7], orders=6 → 31. Bán màu 1: 5,4; màu 2: 7,6,5,4. Tổng = 5+4+7+6+5+4 = 31.

Giải thuật (Tìm kiếm nhị phân ngưỡng giá)

1. Tìm ngưỡng mid sao cho tổng số bóng có giá > mid ≤ orders (binary search trên [0, 1e7]).
2. Với mid tìm được: bán tất cả bóng giá > mid (tổng giá = sum(i*(i+1)/2 - mid*(mid+1)/2)), trừ orders.
3. Bóng còn lại bán hết giá mid: ans += orders * mid.
4. Trả về ans % (10**9+7).

Ví dụ minh họa

def solve(inventory, orders):
    low, high = 0, 10000000
    while low < high:
        mid = (low + high) // 2
        s = sum(i - mid for i in inventory if i > mid)
        if s > orders:
            low = mid + 1
        else:
            high = mid
    mid = (low + high) // 2
    ans = 0
    for i in inventory:
        if i > mid:
            ans += i*(i+1)//2 - mid*(mid+1)//2
            orders -= i - mid
    ans += orders * mid
    return ans % (10**9 + 7)

inventory = [5,7]
orders = 6
print(solve(inventory, orders))

Đầu vào

[6,8,7,11,5,9], [0,0,2], [2,3,5]

Đầu ra

31