Не могу понять логику задачи и по какой логике написан код у задачи
не могу понять как можно решить данную задачу
Владимир представляет на научной выставке свою установку, состоящую из N лампочек, со- единенных в одну цепь. Внезапно он узнает, что установки, как у него, демонстрирующиеся на выставке, должны быть красивой. Установка считается красивой, если в ней некоторое количество лампочек(возможно нулевое) подряд начиная с начала выключено, а оставшаяся часть включена. Например: цепь 0000111 является красивой, а цепь 00010011 нет, где 0 - это выключенная лам- почка, а 1 - включенная. Каждую лампочку на установке можно включить или выключить. Начало выставки уже скоро, и Владимиру нужно сделать свою установку красивой за минимальное количество включений/выключений лампочек. Ниже я предоставил код решения задачи, но я не понимаю алгоритмическую логику, почему именно так сделан код.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
int totalDisabled = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
totalDisabled++;
}
}
int answer = totalDisabled;
int disabled = 0;
int abled = 0;
for (char c : s.toCharArray()) {
if (c == '1') {
abled++;
} else {
disabled++;
}
answer = Math.min(answer, + totalDisabled - abled);
}
}
}
Ответы (1 шт):
Если имеется последовательность 0 и 1, и мы находимся в некоторой позиции этой последовательности (указатель ^
)
011100101110
^
000000111111
### * *
то нетрудно увидеть - для получения красивой последовательности, в которой нули и единицы будут разделяться после данного индекса, нужно:
а) обнулить все единицы, которые встретились до этого момента - в приведённом коде это значение abled
, позиции помечены #
б) установить все нули, которые находятся правее (помечены *
) - а их количество легко найти как разность общего количества нулей totalDisabled
и тех, что уже встретили слева disabled
.
Таким образом, при вычислении минимума (при обходе всех возможных позиций разделения) должно использоваться выражение
totalDisabled - disabled + abled