Поясните логику алгоритма пожалуйста
Вот условие задачи:
На свой день рождения Мила получила строку S, состоящую из символов ‘0’ и ‘1’. Но Мила не считает эту строку красивой, поэтому решила ее исправить! Мила определяет красивой строки следующим образом:
- Разобьем строку на максимально длинные подстроки, состоящие из одинаковых символов.
- Если все эти подстроки получились одинаковой длины, исходная строка считается красивой, а иначе — некрасивой.
Например, строка ‘010101’ разбивается на подстроки ‘0’, ‘1’, ‘0’, ‘1’, ‘0’, ‘1’ и поэтому является красивой, а строка ‘000101’ разбивается на подстроки ‘000’, ‘1’, ‘0’, ‘1’ и поэтому является некрасивой. Другие примеры красивых строк: ‘1’, ‘110011’, ‘00001111’, ‘00000000’. Другие примеры некрасивых строк: ‘011’, ‘010011’, ‘00110100’. Мила просит вас посчитать, сколько минимум символов нужно изменить в строке S, чтобы сделать ее красивой.
Вот код решения задачи:
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String line = sc.next();
int ans = Integer.MAX_VALUE;
for (int i = 1; i <= line.length(); i++) {
if (line.length() % i == 0) {
int minChanges = minChanges(i, line);
ans = Math.min(ans, minChanges);
}
}
System.out.println(ans);
}
private static int minChanges(int rangeLength, String line) {
int rangeCount = line.length() / rangeLength;
int startWithOnes = 0;
int startWithZeroes = 0;
for (int i = 0; i < rangeCount; i++) {
int zeros = 0;
int ones = 0;
for (int j = 0; j < rangeLength; j++) {
char c = line.charAt(j + i * rangeLength);
if (c == '0') {
zeros++;
}
if (c == '1') {
ones++;
}
startWithZeroes += (i % 2 == 0 ? zeros : ones);
startWithOnes += (i % 2 == 0 ? ones : zeros);
}
}
return Math.min(startWithOnes, startWithZeroes);
}
}
Я не могу понять, что вообще считает переменная startWithZeroes и startWithOnes. Я полагал, что она считает сколько надо сделать действий для строки, чтобы каждый подраздел(переменная i) начинался с 0 или 1. Если у нас i делит строку на сегменты по 1 элементу, тогда совпадает с ручными расчетами(на примерах можно убедится). 000101 - изначальная строка, как я понимаю что надо чтобы каждый четный сегмент начинался с 0, а так как сегмент изначально рассматривается по одному числу в сегменте получим 010101(затратили 1 замену). Если начинался с 1 то получим 101010(затратили 5 замен). Тут все совпало.
Дальше берем сегмент по 2(i = 2). если чтобы четные сегменты были нули. Получим 001100 при этом затратив 3 действия. Если чтобы четные сегменты единицы то 110011 затратив 4, а по просмотру дебаг будет startWithOnes = 3, startWithZeroes = 6. Подскажите пожалуйста как тогда надо действовать чтоб совпадать с алгоритмом.
Ответы (1 шт):
$ javac Main.java $ echo 000111 | java Main 0 $ echo 100111 | java Main 2
В этих двух примерах строки различаются на один символ, а ответы на две единицы. Второй ответ ошибочен.
Следовательно, программа содержит ошибку, пояснять логику алгоритма бесполезно.
Если вынести операторы +=
из внутреннего цикла, ошибка пропадает:
------ < < startWithZeroes += (i % 2 == 0 ? zeros : ones); < startWithOnes += (i % 2 == 0 ? ones : zeros); < } ====== > > } > startWithZeroes += (i % 2 == 0 ? zeros : ones); > startWithOnes += (i % 2 == 0 ? ones : zeros); ------
С этим изменением алгоритм становится рабочим. Но всё ещё не эффективен. Можно привести примеры (длин) строк на которых программа будет работать за квадратичное время. Хорошая задача состоит в том чтобы решить её быстрее чем за квадрат.
P.S. Не совсем ответ на ваш вопрос, извините. Скорее объяснение недостатков самого вопроса.
P.P.S. Программы у которых минимум на внешнем цикле, хорошо скрывают ошибки во внутренних циклах. Даже если там наврано, программа продолжает выдавать правдоподобные результаты в большинстве случаев. Часто поймать такую ошибку можно только написав правильную программу и сравнив результаты.
P.P.P.S. Не тратьте время на чужой код, сперва изучите саму задачу.