algorithm - 宿題が解けない (ACM-training)

Question

これを解決する方法がわかりません: http://acm.sgu.ru/problem.php?contest=0&problem=311

これで私を助けてください

セグメントツリーを使用して解決できることは知っていますが、方法がわかりません

score 4 · Accepted Answer

すべての価格を読み取り、セグメントツリーを設定します。セグメントごとに、そのセグメントに含まれる価格の個数と総コストを保存します。それが問題の大部分であり、この回答の残りの部分は、あなたが何かを学ぶことを期待してかなり曖昧になります.
ピースの到着の処理は、セグメントツリーでの単純な O(log n) 時間の降下です。
購入リクエストの処理も、O(log n) 時間の下降と、その後の販売が行われた場合の更新です。更新はセグメントツリーの大部分を横断する可能性があり、償却された意味でのみ高速です。その価格帯にピースがある場合にのみ間隔を入力する必要があり、それらの削除の実行時間は到着時に請求する必要があります。 .

score 2 · Accepted Answer

行ごとにループ:

パラメータ付きの行コマンドを解釈する (ARRIVE/BUY)
モデルを更新 (価格ごとのアイスクリームの数)、モデル: std::map 価格を数量に。
BUY の場合、十分な数のアイスクリームを販売できるかどうかを出力し、最も安いアイスクリームを最初に (マップの最初に) 販売します。

score 0 · Accepted Answer

私は、この問題に対する最良の解決策としてセグメントツリーを売り込んでいないと言わざるを得ません。それらが「最良の」データ構造であるかどうかは、ARRIVE リクエストと BUY リクエストの比率に依存するようです。これは、販売を行うたびに、セグメントの削除後にセグメントツリーを更新するためのかなりの作業が必要になるためです。 .

在庫をリンクされたリストとして保存し、各ノードに特定の単価で販売されるアイテムの数が含まれている場合はどうなるでしょうか。これにより、在庫の挿入と削除のコストが大幅に削減されます。販売できるかどうかを確認するには、目標を達成するか、コストを超えるまで、コストと数量を累積する while ループを繰り返す必要があります。ここでの利点は、販売を行った場合に停止したノードが、次の検索を開始したい在庫の最低コストになることです。ガベージコレクション言語で作業している場合は、リストの先頭への参照を停止したノードに変更するだけで、コードが簡潔になります。

ユニットコストの挿入による新しい在庫の到着は、最悪の場合 O(n) です。ここで、n は到着数です。現実の世界では、これは悪いシステムではないと思います。なぜなら、実際のビジネスでは、多くの販売 (幸せ) と非販売 (不幸せ) が予想されるからです。このアプローチのパフォーマンスが低いのは、ほとんどすべての在庫を購入したいが、それを達成するためのお金が少し足りないという人がたくさんいる場合です.

score 0 · Accepted Answer

たった今（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

編集：コメントを追加

algorithm - 宿題が解けない (ACM-training)

4 に答える 4

Related

Reference