我不知道如何解决这个问题: http ://acm.sgu.ru/problem.php?contest=0&problem=311
请帮我解决这个问题
我知道它可以使用分段树来解决,但我不知道如何
阅读所有价格并设置细分树。对于每个段,存储其价格位于该段的件的数量和总成本。这是大部分问题,这个答案的其余部分将相当模糊,希望你能学到一些东西。
处理片段的到达是分段树中直接的 O(log n) 时间下降。
处理购买请求也是 O(log n) 时间下降,如果进行了销售,则进行更新。更新可能会遍历大量的线段树,并且仅在摊销意义上是快速的——当且仅当该价格范围内有件时才应输入一个间隔,并且应将其移除的运行时间计入到货.
每行循环:
我不得不说,我并不认为分段树是解决这个问题的最佳方法。它们是否是“最佳”数据结构似乎取决于 ARRIVE 与 BUY 请求的比率,因为每次进行销售时,在删除段后更新段树都会有相当多的工作.
如果您将库存存储为链接列表,并且每个节点包含以特定单位成本出售的商品数量,该怎么办。这将使插入和删除库存的成本大大降低。要检查您是否可以进行销售,您必须迭代一个 while 循环来累积成本和数量,直到您达到目标或超过成本。这里的好处是,如果您进行销售,那么您停止的节点现在是您想要开始下一次搜索的最低成本的库存。如果您正在使用垃圾收集语言,您只需将对列表头部的引用更改为您停止的节点,这将使代码简洁。
在到达新库存时,插入单位成本最坏的情况是 O(n),其中 n 是您拥有的到达数量。我认为在现实世界中,这不会是一个糟糕的系统,因为真正的企业会期望大量的销售(快乐)到非销售(不快乐)。这种方法表现不佳的地方是,如果有很多人想要购买几乎你的全部库存,但只是有点缺钱来完成它。
我刚刚(15分钟)写下了这个。示例中仅具有 100k 重复查询的 testet,并且需要 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
编辑:添加评论