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.
这道题考察的是加权随机抽样（weighted random selection）与抽奖概率建模。题意要求购买金额越高，被抽中的概率线性越大，因此不能直接等概率抽奖，而应根据每个客户的购买金额作为权重来决定中奖概率。常见做法是先把所有客户的权重累加，构建前缀和，然后通过随机数定位到对应区间，从而实现按权重返回 K 个赢家；如果需要不重复中奖，还要在每次选中后更新权重或使用更合适的数据结构。
正文完
