Для любого массива, кроме массивов со всеми 0 s, возможны только две операции.Либо переверните n-й элемент, либо переверните элемент прямо перед последним 1 в массиве.
Нам не нужно рассматривать крайний случай только первого элемента, являющегося 1, потому что мы можем добавить любое количество нулейв начало массива, и это не меняет результат, т. е. [1, 0, 0, 0] и [0, 1, 0, 0, 0] требуют одинакового количества минимальных операций, чтобы стать всеми 0 s.
Это означает, что на каждой последовательности 0 и 1 s, одна из операций продвинется на один шаг ближе к 0 s, а другая операция - на один шаг дальше.
Результатом этих наблюдений является то, что у нас фактически есть числовая система, очень похожая на двоичную икаждая операция может рассматриваться как увеличение или уменьшение числа на 1, и это означает, что для каждой последовательности 0 s и 1 s существует эквивалентное двоичное число и десятичное число, которое является числом шагов между этим числом и 0.
Я нашел связь между этой системой и двоичным файлом, которая выглядит следующим образом:
Если мы перебираем массив fОт начала до конца и переворачиваем каждый элемент, который идет после 1, мы получаем эквивалентный двоичный файл.Эта операция должна быть выполнена на месте, это означает, что мы изменяем сам массив во время итерации, и результат каждой итерации влияет на следующую итерацию.У меня нет доказательства того, почему это правильно, может быть, кто-то может предоставить доказательство.
С учетом всего сказанного, сам алгоритм прост.Это в питоне:
a = [1, 0, 0, 0]
# convert to equivalent binary
for i in range(1, len(a)):
a[i] = int(not a[i]) if a[i-1] == 1 else a[i]
# convert to decimal
bin_str = ''.join(map(str, a))
print(int(bin_str, 2))