Amazon wants to build a lottery system. When a customer purchases items worth between $1 and $100, they are entered into the lottery.
Customers who purchase an item for $10 should be 10 times more likely to win the lottery than customers who have purchased an item for $1, i.e. there is a linear relationship between the amount a customer purchased an item for and their probability of winning.
Write a function that takes a list of customers and purchase price as input. As output, it should return K winners.
This problem is about weighted random selection. The winning probability must scale linearly with the purchase amount, so customers cannot be chosen uniformly at random. A common solution is to treat each purchase amount as a weight, build prefix sums over all customers, and use random sampling to pick winners proportional to their weights. If the same customer cannot win more than once, the weights must be updated after each selection or handled with an appropriate data structure.
