大数量级下库存列表均衡分配产品的高效算法需求

Great question! The loop-based approach you're using works for small datasets, but it's inefficient for large targets (like 1e9) because it runs in O(target_total) time. Instead, we can use a mathematical approach that runs in O(n) time (where n is the number of product types) to distribute the purchases evenly while respecting inventory limits.

Here's the optimized algorithm: #

Let's define our variables first:

• inventory: List of integers representing stock for each product type.
• target_total: Total number of items we need to purchase.
• result: List to store how many items to buy from each product.

Step 1: Handle edge case where we can buy all available stock

Calculate the total available inventory—if our target exceeds what's available, we just buy everything:

total_available = sum(inventory)
if target_total >= total_available:
    return inventory.copy()  # Buy every item we have in stock

Step 2: Initialize and adjust for products with limited stock

We start by calculating an initial "base" amount per product, then adjust for products that can't even contribute this base amount (since their inventory is smaller):

n = len(inventory)
remaining_target = target_total
result = [0] * n

# First pass: take all stock from products that can't meet the initial base allocation
initial_base = remaining_target // n
for i in range(len(inventory)):
    if inventory[i] <= initial_base:
        result[i] = inventory[i]
        remaining_target -= inventory[i]
        n -= 1  # This product is fully allocated, remove from future calculations

# Recalculate base and remainder for the remaining products
if n > 0:
    base = remaining_target // n
    remainder = remaining_target % n

    # Second pass: distribute base + optional extra to remaining products
    for i in range(len(inventory)):
        if result[i] == 0:  # Product still has available stock to contribute
            take_amount = base
            if remainder > 0:
                take_amount += 1
                remainder -= 1
            # Ensure we never take more than available (a safety check)
            result[i] = min(take_amount, inventory[i])

Why this works: #

• Efficiency: We only iterate over the inventory list twice, so even for 1e5 product types, this is lightning fast—no matter how large the target total is.
• Even distribution: We first handle products with small inventory (taking all their stock), then split the remaining target evenly among the rest, adding an extra 1 to the first remainder products to use up the leftover count.
• Respects inventory limits: We never take more than what's available for any product.

Example walkthrough: #

Using your sample input inventory = [1,10,10], target_total =10:

1. Total available is 21 >10, so proceed.
2. Initial base =10//3=3. The first product has inventory 1 <=3, so we take all 1. Remaining target becomes 9, n becomes 2.
3. New base=9//2=4, remainder=1.
4. Distribute 4+1=5 to the second product, 4 to the third. Result is [1,5,4]—which matches your valid output.

Customization: #

If you want to prioritize which products get the extra 1 (e.g., prioritize products with higher inventory, or lower), you can sort the remaining products before distributing the remainder. For example, sort indices by inventory descending, then assign the extra to those first.

内容的提问来源于stack exchange，提问作者jalanga