无法解决作业（ACM 培训）

Question

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

请帮我解决这个问题，

我知道可以使用线段树来解决，但我不知道如何解决

Answer 1

1. 读取所有价格并建立线段树。对于每个段，存储价格属于该段的件数和总成本。这就是大部分问题，这个答案的其余部分将相当模糊，希望您能学到一些东西。

2. 处理片段的到达是线段树中直接的 O(log n) 时间下降。

3. 处理购买请求也是一个 O(log n) 时间下降过程，如果进行了销售，则随后进行更新。更新可能会遍历大量的线段树，并且仅在摊销意义上才算快 - 当且仅当存在该价格范围内的片段时才应输入间隔，并且应将其移除的运行时间计入到达时间.

Answer 2

每行循环：

• 解释带参数的行命令（到达/购买）
• 更新模型（每个价格的冰淇淋数量），模型：std::将价格映射到数量。
• 如果是“买入”，则输出是否可以出售足够的冰淇淋，首先出售最便宜的冰淇淋（地图中的第一个）。

Answer 3

我不得不说，我并不认为线段树是解决这个问题的最佳方案。它们是否是“最佳”数据结构似乎取决于到达请求与购买请求的比率，因为每次进行销售时，在删除段后都会有相当多的工作来更新段树。

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

当新库存到达时，单位成本插入最坏的情况是 O(n)，其中 n 是到达的数量。我认为在现实世界中，这不会是一个糟糕的系统，因为真正的企业会期望大量的销售（满意）与非销售（不满意）。如果有很多人想要购买几乎全部库存，但只是缺少资金来实现这一目标，那么这种方法的效果会很差。

Answer 4

我刚才凭空写下了这个（15 分钟）。仅对示例中的 100k 次重复查询进行测试，并且需要 1 秒。

请发表评论，因为这可能是废话：

#!/usr/bin/python
import sys

class store:
    def __init__(self):
        self.sorted = [] # list of tuples (cost, amount) - sorted by cost
        # btw: sorting of tuples is by its elements, so first by element 0
        # that means it is sorted by cost, cheapest first
        self.count = 0 # the global amount of ice in store
        self.mergemap = {} # key = cost, value = tuple of (cost, amount)
        # the mergemap prevents the creation of multiple tuples per priceclass

    def request(self, n, money):
        if self.count < n:
            # if we have less ice in store than was requested -> unhappy
            return False
        pcsleft = n # we count down

        # loop through each priceclass as x
        for x in self.sorted:
            # x[0] is cost, x[1] is the amount of ice of that price in store
            if x[1] < pcsleft and x[0]*x[1] <= money:
                # we found cheap ice, but there is not enough of it
                pcsleft -= x[1]
                money -= x[0]*x[1]
            elif x[1] >= pcsleft and x[0]*pcsleft <= money:
                # theres enough cheap ice, next iteration will not occour
                pcsleft = 0
                money -= x[0]*pcsleft
            else:
                return False # the cheapest ice is too expensive
            if pcsleft == 0 and money >= 0:
                break # happy - break because for-each loop, not while
            if money < 0: # just for kicks, should never happen
                print "error"
                sys.exit(1)
        # when we have cheap enough ice, we remove ice from storage
        # we iterate through the priceclasses like before
        # but when we remove ice from one category, either the loop ends
        # or we completly deplete it  so it can be removed
        while n > 0: # subtract the bought count
            x = self.sorted[0]
            if x[1] > n: # the first priceclass has enough ice
                x[1] -= n
                self.count -= n
                return True # were happy
            elif x[1] == n:
                del(self.mergemap[x[0]]) # remove from mergemap
                self.sorted = self.sorted[1:] # completly remove priceclass
                self.count -= n
                return True
            elif x[1] < n: # 
                n -= x[1]
                self.count -= x[1]
                del(self.mergemap[x[0]])
                self.sorted = self.sorted[1:]

        return True

    def arrive(self, n, cost):
        if cost not in self.mergemap: # we dont have ice in that priceclass
            # create a new tuple, actually list, cause tuples are immutable
            x = [cost, n]
            self.sorted.append(x)
            # resort, should be fast, cause its almost entirely sorted,
            # and python has sorting magic :)
            self.sorted.sort()
            self.mergemap[cost] = x # insert into mergemap
        else:
            # just update the tuple, via its reference in the mergemap
            self.mergemap[cost][1]+=n
            self.count
        self.count += n # keep count correct
        # O(n*logn)

if __name__=='__main__':
    s = store()
    i = 0
    # we read from stdin
    for line in sys.stdin:
        #print line.strip()+" --> ",
        req, count, cost = line.split(' ') # not error tolerant
        if req == 'ARRIVE':
            s.arrive(int(count), int(cost))
        elif req == 'BUY':
            if s.request(int(count), int(cost)):
                print 'HAPPY '+str(i)
            else:
                print 'UNHAPPY '+str(i)
        i+=1
    print s.sorted # print out the left over ice

编辑：添加评论