โปรแกรมหากำไรสูงสุดจากการขายลูกบอลสีต่างๆ ที่ราคาลดลงเรื่อยๆใน Python

ปัญหา

inventory[i] = จำนวนลูกบอลสี i ลูกค้าสั่ง orders ลูก ราคาลูกบอลสีนั้น = จำนวนคงเหลือของสีนั้น (เช่น 6 ลูก → ลูกแรกราคา 6, ลูกถัดไป 5, ...) หากำไรสูงสุด modulo 1e9+7

ตัวอย่าง

inventory = [5,7], orders = 6 → ผลลัพธ์ 31 (ขายสีแรก 2 ลูก: 5,4; สีสอง 4 ลูก: 7,6,5,4; รวม 5+4+7+6+5+4=31)

ขั้นตอนการแก้ปัญหา

1. Binary search หา mid ที่ทำให้ผลรวม max(0, i-mid) ใกล้ orders มากที่สุด
2. low=0, high=10^7 วนจน low < high:
   • mid = (low+high)//2
   • s = sum(max(0, i-mid) for i in inventory)
   • ถ้า s > orders: low = mid+1 มิฉะนั้น: high = mid
3. mid = (low+high)//2
4. ans := 0
5. สำหรับ i ใน inventory:
   • ถ้า i > mid: ans += i*(i+1)//2 - mid*(mid+1)//2; orders -= i-mid
6. ans += orders * mid
7. คืน ans % (10**9+7)

การนำไปใช้งาน (Python)

def solve(inventory, orders):
    low = 0
    high = 10000000
    while low < high:
        mid = (low + high) // 2
        s = 0
        for i in inventory:
            if i > mid:
                s += 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))

อินพุต

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

เอาต์พุต

31