Невозможно решить домашнее задание (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

Цикл на строку:

• команда интерпретации строки с параметрами (ARRIVE / BUY)
• обновить модель (количество мороженых на цену), модель: std :: отобразить цену на количество.
• в случае ПОКУПКИ, укажите, можно ли продать достаточное количество мороженого, продавая сначала самое дешевое мороженое (сначала на карте).

Answer 3

Я только что написал это из своей головы (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

РЕДАКТИРОВАТЬ: добавлены комментарии

Answer 4

Я должен сказать, что я не продаюсь на сегментных деревьях как лучшее решение этой проблемы.То, являются ли они «лучшей» структурой данных, зависит от соотношения запросов ARRIVE и BUY, потому что каждый раз, когда вы совершаете продажу, будет достаточно много работы по обновлению дерева сегментов после удаления сегмента.,

Что если вы сохранили свой инвентарь в виде связанного списка, и каждый узел содержал количество предметов для продажи по определенной цене за единицу.Это значительно снизит стоимость вставки и удаления инвентаря.Чтобы проверить, можете ли вы совершить продажу, вам нужно пройтись по циклу while, накапливая стоимость и количество, пока не достигнете цели или не превысите стоимость.Преимущество здесь в том, что, если вы совершаете продажу, то узел, на котором вы остановились, теперь является самой низкой стоимостью единицы инвентаря, с которой вы хотите начать следующий поиск.Если вы работаете на языке сборки мусора, вы можете просто изменить ссылку на заголовок вашего списка на узел, на котором вы остановились, что сделало бы для краткого кода.

При поступлении нового инвентаря со вставкой стоимости за единицу в худшем случае O (n), где n - это количество прибытий, которое у вас есть.Я думаю, что в реальном мире это не будет плохой системой, потому что реальный бизнес будет ожидать большого количества продаж (счастливых), а не продаж (несчастных).Если этот подход работает плохо, есть много людей, которые хотели бы купить почти весь ваш инвентарь, но им не хватало денег, чтобы выполнить его.