Проблемы с голубем и зерном: найдите время, пока все зерно не съеден

  

Проблема:

     

Есть \ $ n \ $ голубей и \ $ m \ $ зерен. Pigeon \ $ i \ $ ест одно зерно каждый \ $ x_i \ $ секунд. Найдите время, пока все зерна не съедят.

     

Input:

     

Строка с целым числом \ $ m \ $, задающая число зерен, за которым следует строка с \ $ n \ $ целыми числами \ $ x_1, x_2, \ ldots, x_n \ $, дающая время, затраченное каждым голубем на есть одно зерно.

В настоящее время я делаю цикл за каждую секунду и нахожу, сколько зерен за эти секунды съедено. Это с numpy я могу получить хорошую производительность, но для больших входов (\ $ m = 10 ^ {25} \ $ и \ $ n = 300000 \ $) программа работает вечно.

Что я могу сделать математически, чтобы решить эту проблему?

import numpy

def melt(grains,birdTimes):
    counter=0
    counts = numpy.zeros(len(birdTimes,),dtype=numpy.int) 
    birdTimes = numpy.array(birdTimes)
    while (grains>0):
        counts=counts+1
        temp=birdTimes-counts       
        zeroA = numpy.where(temp==0)[0] 
        grains = grains - len(zeroA)
        counts[zeroA] =0
        counter+=1
    return counter
11 голосов | спросил Rohit Srivastava 22 AM00000080000003831 2016, 08:45:38

3 ответа


12

В основном мы ищем наименьшее значение \ $ T \ $, которое удовлетворяет дискретному уравнению

$$ \ left \ lfloor {T \ over x_1} \ right \ rfloor + \ left \ lfloor {T \ over x_2} \ right \ rfloor + \ dots + \ left \ lfloor {T \ over x_n} \ right \ rfloor \ ge m $$

где \ $ \ lfloor {x \ over y} \ rfloor \ $ - операция разделения полов (// в Python). Поэтому мы знаем, что правильная операция деления (/ в Python) также будет правильным решением для этого, хотя и не обязательно с наименьшим возможным \ $ T \ $:

$$ {T \ over x_1} + {T \ over x_2} + \ dots + {T \ over x_n} \ ge m $$

Если вычесть значение времени \ $ T \ $, мы видим, что это просто неравенство вида:

$$ \ mathrm {Time} × \ mathrm {Rate \ of \ Consum} \ ge \ mathrm {Amount \ consumed} $$

и, следовательно,

$$ \ mathrm {Время} \ ge {\ mathrm {Amount \ consumed} \ over \ mathrm {Rate \ of \ Consum}} $$

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

$$ T \ left ({1 \ over x_1} + {1 \ over x_2} + \ dots + {1 \ over x_n} \ right) \ ge m $$

и, следовательно,

$$ T \ ge {m \ over \ left ({1 \ over x_1} + {1 \ over x_2} + \ dots + {1 \ over x_n} \ right)} $$

Вы можете использовать это как эвристику, которая приблизит вас к вашему желаемому значению \ $ T \ $, теперь вашему поисковому пространству просто нужно проверить значения, превышающие приведенный выше результат. Начать с

T = int(M / ((1. / xs).sum()))

Затем итерации вверх до правильного значения, используя ваш метод выбора. Как насчет заполнения наименьшего доступного остатка до следующего кратного? Например:

while True:
    v = (T // xs).sum()
    if v >= M:
        break
    T += (xs - T % xs).min()
return T

Я уверен, что для этого есть решение, близкое к закрытому.

ответил machine yearning 22 PM000000120000000331 2016, 12:01:03
4

Рассчитайте скорость, которую зерна съедают, и просто разделите, чтобы получить результат? Если голубь ест 1 зерно за t секунд, то он съедает 1 /т зерен в секунду, а ставки рассчитываются. Хотя это приведет к ошибке округления в конце, после того, как меньше зерен, чем количество голубей (так как они фактически не потребляют частичные зерна), поэтому вам придется исправить это, если вы заботитесь о точный результат .

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

Просто так, по крайней мере, кое-что об обзоре кода здесь, я просто хочу отметить, что технически ваш код позволяет количеству зерен получить меньше нуля, если несколько голубей попытаются съесть последнее зерно. Не имеет значения, хотя, так как это происходит на одну секунду, но некоторые из голубей могут возражать.

Часто интервалы также подсчитываются вниз, это сохраняет одно вычитание на каждой итерации.

ответил ilkkachu 22 AM000000100000000131 2016, 10:22:01
2

Вы можете быстро вычислить точное общее количество зерен, которые можно было бы съедать за определенный промежуток времени, умножая время отдельно на каждый расход (== усечение деления на секунды на зерно) и сложение результатов. Имея такую ​​функцию в руке, вы можете избежать симуляции всего хода процесса, вместо этого поискать пространство возможных времен. Например:

  1. Вычислить верхнюю границу времени, требуемого как m * max ( x i ).

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

Анализ сложности:

  • Вычисление верхней границы - это O ( n ) для голубей n , потому что для этого требуется найти максимум несортированного списка элементов n .
  • Для вычисления общего количества зерен, потребляемых в течение определенного времени, требуются деления O ( n ) и O ( n ), поэтому также O ( n ).
  • Для ограниченного x i значение начальной верхней границы по времени равно O ( m ).
  • Бинарный поиск по элементам x проверяет элементы O (log x ), а стоимость каждого шага в этом конкретном поиске - O ( n ), поэтому общая стоимость - O ( n log m ).
  • Сравните со сложностью O ( n * m ) для вашего прямого подхода к симуляции и обратите внимание, особенно, что ваша заявленная проблема была связана с производительностью как m становится большим.
ответил PellMel 22 PM00000050000003431 2016, 17:49:34

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132