C++:使用数组创建函数

Question

写一个函数，它有:

input: array of pairs (unique id and weight) length of N, K =< N  
output: K random unique ids (from input array)  

注意:某个Id在输出中被调用多次出现的频率应该越大，它的权重越大。示例:权重为 5 的 id 在输出中出现的频率应该是权重为 1 的 id 的 5 倍。此外，分配的内存量应该在编译时已知，即不应分配额外的内存。

我的问题是:如何解决这个任务？

编辑
谢谢大家的回复!
目前我不明白对的权重是如何影响输出中对的出现频率的，你能给我更清楚的“虚拟”解释它是如何工作的吗？

Answer 1

假设有一个足够好的随机数生成器:

• 对权重求和 (total_weight)
• 重复 K 次:
  • 在 0 和 total_weight 之间选择一个数字(selection)
  • 找到第一对，其中从数组开头到该对的所有权重之和大于或等于selection
  • 将对的第一部分写入输出

您需要足够的存储空间来存储总重量。