Giả sử trong một hội nghị, có hai loại người. Loại người đầu tiên thích bữa trưa chay, và loại còn lại thích bữa trưa không ăn chay. Nhưng số lượng gói có hạn, và nếu người ăn chay nhận được gói không ăn chay hoặc ngược lại; họ sẽ không lấy gói đó và đợi cho đến khi nhận được gói ưa thích của họ. Vì vậy, hai loại gói và người khác nhau được ký hiệu là 0 cho người ăn chay và 1 cho người không ăn chay. Bây giờ chúng ta được cung cấp hai mảng, một mảng chứa n số gói thực phẩm được ký hiệu là 0 và 1 và một mảng khác chứa hàng đợi gồm m số người và sở thích của họ được ký hiệu là 0 và 1. Vì vậy, nếu một người không nhận được gói ưa thích, họ nhập lại hàng đợi ở cuối và đợi gói ưa thích của họ. Vì vậy, chúng tôi phải tìm ra số người không có gói thực phẩm để chúng tôi có thể sắp xếp các gói ưa thích của họ.
Vì vậy, nếu đầu vào là people =[0,1,1,0], packets =[0, 1, 0, 0], thì đầu ra sẽ là 1.
Vì vậy, hai người thích thực phẩm không ăn chay và chỉ có một gói không ăn chay. Người đầu tiên trong hàng thích không ăn chay nhận được gói đó và người kia tiếp tục chờ đợi vì không có gói nào khác. Vì vậy, đầu ra là 1.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
temp_arr:=một danh sách mới chứa các giá trị 0 và 0
-
đối với mỗi người trong mỗi người, làm
-
temp_arr [person]:=temp_arr [person] + 1
-
-
k:=0
-
trong khi k
-
nếu temp_arr [packets [k]]> 0, thì
-
temp_arr [packets [k]]:=temp_arr [packets [k]] - 1
-
-
nếu không,
-
đi ra từ vòng lặp
-
-
k:=k + 1
-
-
kích thước trả về của gói - k
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(people, packets):
temp_arr = [0,0]
for person in people:
temp_arr[person] += 1
k = 0
while k < len(packets):
if temp_arr[packets[k]]>0:
temp_arr[packets[k]]-=1
else:
break
k += 1
return len(packets) - k
print(solve([0,1,1,0], [0, 1, 0, 0])) Đầu vào
[0,1,1,0], [0, 1, 0, 0]
Đầu ra
1