すべての人がPythonで2台のマシンに投票できるかどうかを確認します

nという数字がn人を表し、2台の同じ投票機があるとします。また、time [i]がi番目の人が任意のマシンに投票するために費やした合計時間を表すような、サイズnのtimeという配列もあります。一度に、2台のマシンのそれぞれに1人だけがそこにいることができます。また、マシンが稼働している最大許容時間を表す別の値xがあります。すべての人が投票できるかどうかを確認する必要があります。

したがって、入力がn =3、x =7、time =[3、5、3]の場合、出力はTrueになります。時間t0で、0人目が最初のマシンに移動し、1人目が2番目のマシンに移動するためです。現在、t3の時点で最初のマシンは無料です。これで、2人目が最初のマシンに移動し、時間t5で2番目のマシンが無料になり、時間t6で最初のマシンが無料になるため、すべての参加者が時間内に投票しました。

これを解決するには、次の手順に従います-

• total_sum：=時間のすべての要素の合計
• total_sum <=xの場合、
  • Trueを返す
• リストの時間を並べ替える
• prev_sum：=時間と同じサイズで、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の場合、do
    • 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