检查Python中是否所有人员都能在两台机器上投票

假设我们有一个数字n表示n个人，并且有两台相同的投票机。我们还有一个名为time大小为n的数组，其中time[i]表示第i个人在任何机器上花费的总时间。在同一时间点，每台机器上只能有一人。我们还有一个值x，表示机器可运行的最大允许时间，我们必须检查是否所有人员都能投票。

因此，如果输入类似于n = 3，x = 7，time = [3, 5, 3]，则输出为True。因为在时间t0，第0个人去第一台机器，第1个人去第二台机器。现在在时间t3，第一台机器空闲。现在第2个人去第一台机器，在时间t5第二台机器空闲，在时间t6第一台机器空闲，所以所有参与者都在规定时间内投票。

为了解决这个问题，我们将遵循以下步骤：

  • total_sum := time所有元素的总和
  • 如果total_sum <= x，则
    • 返回True
  • 对列表time进行排序
  • prev_sum := 一个与time大小相同的数组，并填充0
  • prev_sum[0] := time[0]
  • 对于范围从1到prev_sum大小的i，执行：
    • prev_sum[i] := prev_sum[i - 1] + time[i]
  • 对于范围从0到prev_sum大小的i，执行：
    • 对于范围从i + 1到prev_sum大小-1的j，执行：
      • temp_sum := prev_sum[i] + (total_sum - prev_sum[j])
      • 如果temp_sum <= x并且total_sum - temp_sum <= x，则
        • 返回True
  • 返回False

让我们看看下面的实现来更好地理解：

示例

在线演示

def solve(n, x, time):
   total_sum = sum(time)
   if total_sum <= x:
      return True
   time.sort()
   prev_sum = [0 for i in range(len(time))]
   prev_sum[0] = time[0]
   for i in range(1, len(prev_sum)):
      prev_sum[i] = prev_sum[i - 1] + time[i]
   for i in range(0, len(prev_sum)):
      for j in range(i + 1, len(prev_sum)):
         temp_sum = (prev_sum[i] + (total_sum - prev_sum[j]))
         if temp_sum <= x and total_sum - temp_sum <= x:
            return True
   return False
n = 3
x = 7
time = [3, 5, 3]
print(solve(n, x, time))

输入

3, 7, [3, 5, 3]

输出

True

更新于：2020-12-30

72 次浏览

启动您的职业生涯

完成课程获得认证

开始
广告