Chương trình gom nhóm các số 1 với số lần hoán đổi tối thiểu Python

Cho chuỗi nhị phân input_str chứa 0 và 1. Nhiệm vụ gom tất cả số 1 lại với nhau bằng cách hoán đổi các số 1 liền kề. Tìm số lần hoán đổi tối thiểu.

Ví dụ: input_str = "10110101" → 4 (biến đổi: 10110101→01110101→01111001→01111010→01111100).

Giải thuật toán học

1. Thu thập vị trí của tất cả số 1 vào mảng one
2. Tìm vị trí trung vị mid = len(one) // 2
3. Tổng số lần hoán đổi = sum(|one[mid] - one[i]| - |mid - i|) cho mọi i
4. Trả về max(0, res)

Ví dụ triển khai

def solve(input_string):
    one = [i for i in range(len(input_string)) if input_string[i] == "1"]
    mid = len(one) // 2
    res = 0
    for i in range(len(one)):
        res += abs(one[mid] - one[i]) - abs(mid - i)
    return 0 if res < 0 else res

print(solve('10110101'))

Đầu vào

'10110101'

Đầu ra

4