Блог

Недавно я столкнулся с тем, что кажется довольно интересной игрой, в которой предлагается реализовать как методы с двумя указателями, так и методы с префиксной суммой в большом наборе данных. Вот сама задача:

Представьте, что существует массив v длиной k, где k (k<=10**5) представляет количество записей, состоящих из двух чисел: A (так называемая куча) и N(количество), например:

 k = 3
v = [[2, 2], [3, 2], [2, 1]]
 

A ( v[i][0] ) — это значение, а N ( v[i][1] ) — количество раз, когда это значение задается. Другими словами, N — это частота A.

Теперь нам нужно выбрать минимум A, начиная с обоих концов списка, вычесть его из текущих позиций и добавить к следующим. Затем мы продолжаем делать это до тех пор, пока в середине не останется всего две или одна попытка. Другими словами, на каждом шаге мы выбираем самую маленькую стопку и вычитаем ее с обоих концов, пока не останется одна или две стопки.

Ответ должен включать две строки: первая содержит либо «1», либо » 2 » в зависимости от того, сколько стопок осталось, а вторая-сам результат.

Для упрощения мы можем представить стопки в виде простого списка, который выглядит следующим образом:

 v = [2, 2, 3, 3, 2] 
 

Мы выбираем минимум с левого и правого концов (2), вычитаем его и добавляем к следующим значениям:

 v = [0, 4, 3, 5, 0]
 

Минимум 4 и 5 равен 4, поэтому мы вычитаем 4 и получим две стопки.

 v = [0, 0, 11, 1, 0]
 

И результат таков:

 2
11 1
 

Мой код таков:

 k = int(input())
a = []
for _ in range(k):
    A, N = map(int, input().split())
    x = [A] * N
    a  = x


l = 0
r = len(a)-1
while r - l > 1:
    s = min(a[l], a[r])
    a[l] -= s
    a[r] -= s
    a[l 1]  = s
    a[r-1]  = s
    if a[l] == 0:
       l  = 1
    if a[r] == 0:
       r -= 1

if a[r] == 0 or a[r]==a[l]:
    print(1)
    print(a[l])
      
else:
    print(2)
    print(a[l], a[r])
 

Это решение не соответствует ограничению по времени (2 секунды) при k = 10**5, поскольку оно требует преобразования массива в простой список, а также едва использует префиксную сумму. Я точно знаю, что существует гораздо более быстрое решение с префиксной суммой, дополнительными переменными и сохранением массива в заданном виде. Буду признателен за любые советы о том, как я могу ускорить этот код.
Чтобы предотвратить любые комментарии, связанные с языком: игра предназначена для любого языка программирования, поэтому ограничение по времени не относится конкретно к python.

Я не дам вам ответа, но я укажу путь, чтобы найти ответ.

Хитрость не в том, чтобы выполнить алгоритм быстрее, а в том, чтобы выяснить результат применения алгоритма, выполняя при этом меньше работы. Чтобы сделать это проще, я собираюсь заменить алгоритм еще более медленным, о котором, как оказалось, легче рассуждать.

Вместо того, чтобы вычитать меньшее с обеих сторон, добавляя к следующему, давайте просто вычтем по 1 с каждой стороны, добавляя к следующему. Так что ваш пример должен был бы начаться:

 [2, 2, 3, 3, 2]
[1, 3, 3, 4, 1]
[0, 4, 3, 5, 0]
...
 

Давайте начнем рассуждать.

Сначала предположим, что у нас есть A один конец, сколько шагов требуется, чтобы продвинуться по этой стороне за один раз? Ответ прост A .

Что произойдет, если за нами A последует k a s? Для продвижения по блоку до тех пор, пока все не будет сложено на последнем элементе, требуется

 A   A a   A 2a   ... A (k-1)a
    = kA   (1   2   ...   (k-1))a
    = kA   k(k-1)a/2
 

В этот момент у последнего элемента теперь есть A ka элементы.

Итак, теперь, не расширяя блок, мы можем вычислить, сколько работы требуется, чтобы пройти через него с помощью простой формулы. Мы можем сделать это и на другой стороне. Таким образом, не расширяясь, мы можем начать потреблять целые блоки с каждой стороны, пока не достигнем середины на последних 2 или 3 блоках. Тогда мы должны быть осторожны, но мы можем точно определить, где находится один из них, когда другая сторона завершает блок. Затем мы можем разделить эти блоки на более мелкие элементы блоков и продолжать продвигаться, пока не найдем не более 3 элементов массива между нашими наступающими фронтами, где они встретятся. А затем мы несколько раз применяем оригинальный алгоритм, чтобы получить точный ответ.

Но вы должны уметь проходить целые блоки с помощью одного арифметического вычисления, чтобы сделать это достаточно быстро.

Удачи в выполнении всех граничных условий правильно!