主页 / 问题 / 1591668
Accepted
Никита Бауэр
Asked:2024-08-23 16:18:09 +0000 UTC2024-08-23 16:18:09 +0000 UTC

KuznechiK - 任务

  • 772

一只蚱蜢坐在一条长度为 n 的格子条前面。每个单元格包含一个数字。 KuznechiK 可以向前跳跃 1,2,... k 个单元格。您需要到达最右边的单元格，同时收集尽可能少的数量。输入是 n、k 和 n 个像元值。我不知道如何以最佳方式解决问题。目前，我只想使用该平台，在每个新单元格后添加一个新值，并在必要时删除旧单元格。但事实证明，每次我都必须在牌组中寻找新的最小值。有更好的选择吗？

алгоритм

1 个回答

  1. Best Answer

    1. 两个栈上排队

    最小感知队列构建在两个最小感知堆栈上。

    # очередь, которая умеет возвращать минимум всех элементов в ней
class MinQueue:
    def __init__(self):
        self._s1 = []     # первый стек хранит только значения без минимумов
        self._s1_min = [] # текущий минимум всего первого стека
        self._s2 = []     # второй стек хранит только минимумы без значений

    # константа
    def len(self):
        return len(self._s1) + len(self._s2)

    # константа
    def min(self, default=None):
        # минимум по обоим стекам
        return min(self._s1_min + self._s2[-1:], default=default)

    # константа
    def push(self, v):
        self._s1.append(v)                       # добавить в первый стек
        self._s1_min = [min([v] + self._s1_min)] # обновить минимум первого стека

    # амортизированная константа
    def pop(self):
        if not self._s2: # если второй стек пуст
            while self._s1: # пока первый стек не пуст
                # положить во второй стек новый минимум
                self._s2.append(min([self._s1.pop()] + self._s2[-1:]))
            self._s1_min = [] # стереть минимум первого стека
        self._s2.pop()


# последовательное чтение целых чисел из входного потока
def ints():
    while True:
        yield from map(int, input().split())


def main():
    it = ints()

    n = next(it) # число клеток в полоске
    k = next(it) # максимальная длина прыжка

    # содержит минимальные суммы для последовательных клеток
    q = MinQueue()
    for _ in range(n):
        v = q.min(default=0) + next(it) # сердце алгоритма
        if q.len() >= k:
            q.pop()
        q.push(v)

    print(v) # печать последнего элемента очереди


main()

    2. 升序队列

    这个想法是借用MBo的回答。普通双端队列，但是新元素从队列末尾删除大于或等于它们的元素。很明显，这些大的因素未来将无法影响最小的因素。该队列在每个时间点都按升序排列。

    import collections


# очередь, которая умеет возвращать минимум всех элементов в ней
class MinQueue:
    def __init__(self):
        self._i = 0 # индекс хвоста очереди
        self._q = collections.deque() # (индекс, значение), значения возрастают

    # константа
    def len(self):
        return self._i - self._q[0][0] if self._q else 0

    # константа
    def min(self, default=None):
        return self._q[0][1] if self._q else default

    # амортизированная константа
    def push(self, v):
        while self._q and self._q[-1][1] >= v:
            self._q.pop()
        self._q.append((self._i, v))
        self._i += 1

    # константа
    def pop(self):
        self._q.popleft()

    比较

    两个队列都为解决问题提供了线性复杂度。哪个常数更好？

    表中，“两个堆栈”和“有序队列”的时间用分数表示。有序队列注意到k变化很小- 对于随机数据，该队列很短。 “两堆”总是更糟糕。有时两次，有时更多。

    n=10 5 n=10 6 n=10 7
    k=10 0 0.24 / 0.13 2.62 / 1.64 26.98 / 17.05
    k=10 1 0.23 / 0.12 2.27 / 1.22 23.77 / 13.66
    k=10 2 0.21 / 0.12 2.14 / 1.17 22.32 / 12.00
    k=10 3 0.21 / 0.12 2.15 / 1.19 22.62 / 11.86
    k=10 4 0.22 / 0.12 2.39 / 1.19 35.37 / 12.31
    k=10 5 0.18 / 0.12 2.39 / 1.21 36.00 / 11.92
    k=10 6 2.02 / 1.25 41.26 / 12.30
    k=10 7 49.78 / 12.04

    路线恢复

    如果将路由（索引列表）添加到队列元素中，则可以将其恢复：

    def main():
    it = ints()

    n = next(it) # число клеток в полоске
    k = next(it) # максимальная длина прыжка

    # содержит пары (минимальная сумма, маршрут) для последовательных клеток
    q = MinQueue()
    for i in range(n):
        v, r = q.min(default=(0, None))
        if q.len() >= k:
            q.pop()
        v += next(it) # сердце алгоритма
        r = i, r
        q.push((v, r))

    print(v, r) # печать последнего элемента очереди
    • 1

相关问题