Ваша ошибка проявляется в строке i 11 (12-я строка, если считать естественно / на основе 1).
P T P P T P T P T P T P T T T P P P
В этой строке 8 воров. Их всех можно поймать. В следующей строке + обозначает полицейского или полицейского, успешно поймавшего вора, тогда как - означает того, кто его не поймает.
+ T - + T + T + T + T + T T T + + -
(Первый вор может быть пойман любым полицейский слева или справа, это не имеет значения для подсчета. Есть еще больше возможных вариантов того, кто поймает первых двух воров.)
Ваша программа «ловит» только 7 из 8 воров. . Перед этим рядом у вас есть счет 68, что я считаю правильным. После ряда ваш счет 75, он должен быть 76.
В ряду первые 5 воров пойманы должным образом. Что теперь делает полицейский с индексом 11? Вор слева уже пойман. Справа трое воров. Ваш второй самый внутренний l oop отсчитывается от y = j+K = 11 + 2 = 13, поэтому ловит вора с индексом 13, оставляя вора с индексом 12 непойманным. Следующий полицейский имеет индекс 15. Когда K равно 2, он / она не может поймать вора с индексом 12, расстояние слишком велико.
Изменить: моя идея решения. Поскольку вы опубликовали свое решение, я думаю, что могу опубликовать свое, ничего не испортив. Моя идея состоит в том, чтобы каждый вор обыскивал слева направо полицейского, который сможет поймать этого вора. Я начну поиск с того места, где остановился предыдущий поиск. Это гарантирует, что каждый полицейский поймает только одного вора.
char[] row = { 'P', 'T', 'P', 'P', 'T', 'P', 'T', 'P', 'T',
'P', 'T', 'P', 'T', 'T', 'T', 'P', 'P', 'P' };
int k = 2; // The uppercase K from the problem
int count = 0;
// Index from where to search for the next police officer to catch a thief
int pix = 0;
for (int ix = 0; ix < row.length; ix++) {
if (row[ix] == 'T') {
if (pix < ix - k) {
pix = ix - k;
}
int searchLimit = Math.min(row.length, ix + k + 1);
while (pix < searchLimit && row[pix] != 'P') {
pix++;
}
if (pix < searchLimit) { // Found
count++;
pix++;
}
}
}
System.out.println(count);
Вывод:
8
Я не использую никаких вспомогательных структур данных, и я не изменяю входной массив. Я считаю, что этот алгоритм эффективен (я не пробовал его на хакерской земле).
Проблема симметрична для полицейских и воров, поэтому можно сделать это и наоборот, для каждого полицейского, ищущего по адресу вор, чтобы поймать, он будет работать так же.
Если вызов Math.min() кажется необычным, вместо этого используйте тернарный оператор ? : или конструкцию if - else.
PS Может быть, на hackerearth было бы более уместно иметь P для полицейского и H для хакера и спрашивать, сколько хакеров сбежали, не будучи пойманными полицией. Шучу.