Giả sử chúng ta có n người và hai máy bỏ phiếu giống hệt nhau. Có mảng time kích thước n, time[i] là thời gian người thứ i cần để bỏ phiếu. Một lúc chỉ có một người trên mỗi máy. Có giá trị x là thời gian tối đa cho phép máy hoạt động. Cần kiểm tra xem tất cả mọi người có kịp bỏ phiếu hay không.
Ví dụ, n = 3, x = 7, time = [3, 5, 3], đầu ra True. Tại t=0: người 0 vào máy 1, người 1 vào máy 2. Tại t=3 máy 1 rảnh, người 2 vào máy 1. Tại t=5 máy 2 rảnh, tại t=6 máy 1 rảnh -> tất cả kịp bỏ phiếu.
Các bước giải quyết:
- total_sum := tổng time.
- Nếu total_sum <= x, trả về True.
- Sắp xếp time.
- prev_sum := mảng tiền tố của time.
- Duyệt i từ 0 đến len(prev_sum)-1:
- Duyệt j từ i+1 đến len(prev_sum)-1:
- temp_sum := prev_sum[i] + (total_sum - prev_sum[j]).
- Nếu temp_sum <= x và total_sum - temp_sum <= x, trả về True.
- Duyệt j từ i+1 đến len(prev_sum)-1:
- Trả về False.
Xem ví dụ dưới đây để 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] * 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(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