3

所以假设超市的自助结账台有一个队列。我正在尝试编写一个函数来计算所有客户结帐所需的总时间！

输入：

客户：代表队列的正整数数组。每个整数代表一个客户，其值是他们结账所需的时间。

n：一个正整数，结账台数。

输出：

该函数应返回一个整数，即所需的总时间。例子：

queue_time([5,3,4], 1)
# should return 12
# because when n=1, the total time is just the sum of the times

queue_time([10,2,3,3], 2)
# should return 10
# because here n=2 and the 2nd, 3rd, and 4th people in the 
# queue finish before the 1st person has finished.

queue_time([2,3,10], 2)
# should return 12

只有一个队列服务于许多收银台，队列的顺序永远不会改变。队列中的最前面的人（数组/列表中的第一个元素）一旦空闲就进入直到它。我试过这个，但它不能正常工作，我不知道如何让下一个人进入，直到它打开。

def queue_time(customers, n)
  if customers == []
    n=0
  else
    x= customers.reduce(:+) / n 
    if x < customers.max
      customers.max
    else 
      x
    end
  end
end

例如，测试

customers = [751, 304, 2, 629, 36, 674, 1] 
n = 2
expected: 1461, instead got: 1198

. 谢谢 ：-）

4

4 回答 4

5

给定输入：

customers = [751, 304, 2, 629, 36, 674, 1]
n = 2

您可以创建一个数组：（每个数组本身就是一个数组）

tills = Array.new(n) { [] }
#=> [[], []]

现在，对于每个客户，您将其价值添加到最短直到：

customers.each do |customer|
  tills.min_by(&:sum) << customer
end

最后，这给了你：

tills
#=> [[751, 36, 674], [304, 2, 629, 1]]

第一个的总和为 1,461。

于 2021-03-01T20:19:25.703 回答
2 
def queue_time(time_required, n)
  remaining_time_by_line = Array.new(n) { 0 }
  curr_time = 0
  time_required.each do |t|
    wait_time, line_assigned = remaining_time_by_line.each_with_index.min_by(&:first)
    curr_time += wait_time
    remaining_time_by_line.map! { |rt| rt - wait_time }
    remaining_time_by_line[line_assigned] = t
  end
  curr_time + remaining_time_by_line.max
end

queue_time([5,3,4], 1)
  #=> 12
queue_time([10,2,3,3], 2)
  #=> 10
queue_time([2,3,10], 2)
  #=> 12 
queue_time([2,3,4,1,2,5], 3)
  #=> 8
queue_time([751, 304, 2, 629, 36, 674, 1], 2)
  #=> 1461

puts在用语句加盐之后，我可以通过执行该方法来最容易地解释计算。

def queue_time(time_required, n)
  remaining_time_by_line = Array.new(n) { 0 }
  curr_time = 0
  time_required.each do |t|
    wait_time, line_assigned = remaining_time_by_line.each_with_index.min_by(&:first)
    curr_time += wait_time
    puts "\ntime required, t = #{t}"
    puts "line_assigned = #{line_assigned}"
    puts "wait_time = #{wait_time}"
    puts "curr_time = #{curr_time}"
    remaining_time_by_line.map! { |rt| rt - wait_time }
    remaining_time_by_line[line_assigned] = t
    puts "remaining_times_by_line = #{remaining_time_by_line}"   
  end
    puts "\nremaining_time_by_line.max = #{remaining_time_by_line.max}"
    tot = curr_time + remaining_time_by_line.max
    puts "curr_time + remaining_time_by_line.max = #{tot}"
    tot
end

queue_time([2,3,4,1,2,5], 3)
  #=> 8

显示以下内容。

time required, t = 2
line_assigned = 0
wait_time = 0
curr_time = 0
remaining_times_by_line = [2, 0, 0]

time required, t = 3
line_assigned = 1
wait_time = 0
curr_time = 0
remaining_times_by_line = [2, 3, 0]

time required, t = 4
line_assigned = 2
wait_time = 0
curr_time = 0
remaining_times_by_line = [2, 3, 4]

time required, t = 1
line_assigned = 0
wait_time = 2
curr_time = 2
remaining_times_by_line = [1, 1, 2]

time required, t = 2
line_assigned = 0
wait_time = 1
curr_time = 3
remaining_times_by_line = [2, 0, 1]

time required, t = 5
line_assigned = 1
wait_time = 0
curr_time = 3
remaining_times_by_line = [2, 5, 1]

remaining_time_by_line.max = 5
curr_time + remaining_time_by_line.max = 8
于 2021-03-01T20:16:53.180 回答
2

您的问题属于离散事件模拟 (DES) 建模类别。对于简单模型，DES 有时可以通过循环和条件处理（如提供的其他答案中所示），但如果您计划扩展此模型或构建更复杂的模拟，您将需要使用某种事件调度框架，如所述在这个冬季模拟会议教程中。一个名为simplekit的 gem提供了教程中概念的 Ruby 实现。（完全披露——我是论文和宝石的作者。）

一个快速的总结是一个“事件”发生在一个离散的时间点并更新系统状态。它还可以安排更多活动。DES 框架维护一组未决事件作为优先级队列，以便事件以正确的顺序发生，尽管事件被调度和执行之间存在时间延迟。所有这些都由框架提供的方法相对透明地处理。

这是具有不同参数化的模型的实现，并带有大量注释：

require 'simplekit'

class MyModel
  include SimpleKit

  # Constructor - initializes the model parameters.
  # param: service_times - An array of service times for each customer
  # param: max_servers - The total number of servers in the system.
  def initialize(service_times, max_servers)
    @service_times = service_times.clone
    @max_servers = max_servers
  end

  # Initialize the model state and schedule an initial set of events.
  def init
    @num_available_servers = @max_servers
    # As long as servers remain available and there are customers
    # remaining, schedule the end_service for the next customer
    # to occur after a delay equal to the customer's service time.
    # The number of available servers gets reduced by one.
    while @num_available_servers > 0 && !@service_times.empty? do
      schedule(:end_service, @service_times.shift)
      @num_available_servers -= 1
    end
  end

  # Every time there's an end of service, see if there's another customer
  # waiting in line.  If so, schedule their end_service (and the current
  # server remains tied up), otherwise the current server gets freed up.
  #
  # This model will terminate when there are no more events scheduled,
  # which happens when all the end_services have completed.
  def end_service
    if @service_times.empty?
      @num_available_servers += 1
    else
      schedule(:end_service, @service_times.shift)
    end
  end
end

model_params = [
  [[5,3,4], 1],
  [[10,2,3,3], 2],
  [[2,3,10], 2],
  [[2,3,4,1,2,5], 3],
  [[751, 304, 2, 629, 36, 674, 1], 2]
]

# SimpleKit models track and update the model_time automatically for you,
# so the current_model's model_time reflects what time it was in the
# model when the last event occurred.
model_params.each do |svc_times, servers|
  current_model = MyModel.new(svc_times, servers)
  current_model.run
  puts "#{svc_times}, #{servers} => #{current_model.model_time}"
end

产生以下输出：

[5, 3, 4], 1 => 12.0
[10, 2, 3, 3], 2 => 10.0
[2, 3, 10], 2 => 12.0
[2, 3, 4, 1, 2, 5], 3 => 8.0
[751, 304, 2, 629, 36, 674, 1], 2 => 1461.0
于 2021-03-01T21:26:59.237 回答
1

与 Stefan 的回答基本相同。不同之处在于，此答案仅跟踪每次结账时的总和，而不是跟踪客户并在每次新客户到达时重新汇总他们的值。

def queue_time(customers, n)
  till  = Struct.new(:sum)
  tills = Array.new(n) { till.new(0) }

  customers.each do |customer| 
    tills.min_by(&:sum).sum += customer
  end

  tills.map(&:sum).max
end
于 2021-03-01T21:57:19.867 回答