无法解决作业(ACM-training)

Question

我不知道如何解决这个问题：http://acm.sgu.ru/problem.php?contest=0&problem=311

请帮我解决这个问题

我知道使用分段树可以解决这个问题，但我不知道如何解决

Answer 1

1. 读取了所有的价格并建立了一个细分树。对于每个细分市场，存储其价格位于该细分市场的件数和总成本。这就是最大的问题，剩下的答案将相当模糊，希望您了解到，在段树中，件的到达是一个简单的O( something.
2. Handling n)-time下降。
3. 处理购买请求也是O(log )-time下降，然后在完成销售后进行更新。更新可能会遍历大量的分段树，并且只有在摊销意义上才是快速的-当且仅当存在该价格范围内的部件时，才应输入间隔，并且删除这些部件的运行时间应计入到达时间。

Answer 2

每行循环：

• 使用参数解释行命令模型(每价格的冰激凌数量)，型号:std：：将价格映射到数量。
• 在购买的情况下，输出是否可以销售足够的冰激凌，首先销售最便宜的冰激凌(地图中的第一个)。

Answer 3

我不得不说，我不相信片段树是这个问题的最佳解决方案。它们是否是“最好的”数据结构似乎取决于到达与购买请求的比率，因为每次你做一次销售，在删除一个段之后，将有相当多的工作来更新你的段树。

如果您将库存存储为链表，并且每个节点包含以特定单位成本出售的商品数量，会发生什么情况？这将使插入和移除库存的成本大大降低。要检查是否可以进行销售，您必须迭代while循环，累积成本和数量，直到达到目标或超过成本。这里的优点是，如果您进行了销售，那么您停止的节点现在是您想要开始下一次搜索的库存的最低成本。如果您正在使用垃圾收集语言，您只需将列表头部的引用更改为您停止的节点，这将使代码简洁。

在有单位成本的新库存到达时，插入的最坏情况是O(n)，其中n是您拥有的到达数量。我认为在现实世界中，这不会是一个糟糕的系统，因为一个真正的企业会期望大量的销售(高兴)到非销售(不愉快)。这种方法表现不佳的地方是，如果有很多人想买几乎所有的库存，但只是有点缺钱来完成它。