Kiểm tra xem tất cả mọi người có thể bỏ phiếu cho hai máy bằng Python hay không

Giả sử chúng ta có một số n biểu thị n người và có hai máy bỏ phiếu giống nhau. Chúng ta cũng có một mảng được gọi là thời gian có kích thước n sao cho thời gian [i] đại diện cho tổng thời gian của người thứ i để bỏ phiếu trên bất kỳ máy nào. Tại một thời điểm tức thì, chỉ một người có thể ở đó trên mỗi máy trong số hai máy. Chúng tôi cũng có một giá trị khác là x, đại diện cho thời gian tối đa cho phép mà máy móc hoạt động, chúng tôi phải kiểm tra xem tất cả mọi người có thể bỏ phiếu của họ hay không.

Vì vậy, nếu đầu vào là n =3, x =7, time =[3, 5, 3], thì đầu ra sẽ là True. Vì tại thời điểm t0 người thứ 0 đi máy thứ nhất và người thứ 1 đi máy thứ hai. Bây giờ tại thời điểm t3 máy đầu tiên là miễn phí. Bây giờ người thứ 2 đến máy thứ nhất và tại thời điểm t5 máy thứ hai miễn phí và tại thời điểm t6 máy thứ nhất miễn phí nên tất cả những người tham gia đã bỏ phiếu kịp thời.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• total_sum:=tổng của tất cả các yếu tố của thời gian
• nếu total_sum <=x, thì
  • trả về True
• sắp xếp thời gian của danh sách
• prev_sum:=một mảng có kích thước bằng với thời gian và điền bằng 0
• prev_sum [0]:=time [0]
• đối với tôi trong phạm vi từ 1 đến kích thước của pres_sum, hãy thực hiện
  • pres_sum [i]:=pres_sum [i - 1] + thời gian [i]
• đối với tôi trong phạm vi từ 0 đến kích thước của pres_sum, hãy thực hiện
  • đối với j trong phạm vi i + 1 đến kích thước của pres_sum - 1, thực hiện
    • temp_sum:=pres_sum [i] + (total_sum - pres_sum [j])
    • nếu temp_sum <=x và total_sum - temp_sum <=x, thì
      • trả về True
• trả về Sai

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

3, 7, [3, 5, 3]

Đầu ra

True