Возникла проблема с Каттис, и я предполагаю, что это крайний случай.

Question

Мне нужна была бы помощь с упражнением Каттис "Соседский дозор". Я провалил 11-й тест из-за неправильного ответа, и понятия не имею, почему. Любая помощь приветствуется.

Дженнифер была назначена капитаном районной вахты и теперь отвечает за вахту на своей улице.

Улица Дженнифер состоит из домов только с одной стороны дороги. У нее есть план домов, в которых будет находиться районная стража, и она хочет знать, насколько этот план безопасен. Прогулка от одного дома к другому (не обязательно отдельному) считается безопасным, если на маршруте есть хотя бы один дом, который является домом соседской стражи. Рейтинг безопасности плана - это количество безопасных прогулок по улице. Поскольку прогулка является безопасной или небезопасной, при движении в любом направлении она не учитывается дважды в рейтинге безопасности.

Скажите Дженнифер рейтинг безопасности ее плана. Ввод

Первая строка входных данных содержит два целых числа N (1≤N≤200000) - количество домов на улице, и K (0≤K≤N) - количество домов наблюдения за окрестностями на плане Дженнифер. Дома пронумерованы 1,…,N.

Следующие K строк описывают соседские сторожевые дома. Каждая из этих строк содержит единственное целое число H (1≤H≤N), которое является номером дома соседского сторожевого дома. Номера домов указаны в строго возрастающем порядке.

Выход

Отобразите рейтинг безопасности ее системы (покажите количество возможных безопасных прогулок).

public class NeighborhoodWatch {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String first[] = br.readLine().split(" ");
        int n = Integer.parseInt(first[0]);
        int k = Integer.parseInt(first[1]);
        int ks[] = new int[k];
        int x=0;
        int y=k;
        while (y>0) {
            ks[x] = Integer.parseInt(br.readLine());
            x++;
            y--;
        }
        Arrays.sort(ks);
        long count = 0;
        //This loop runs through the safe houses(if they exist).
        //It takes the remaining number of houses from the sad house onwards and multiplies it with the number of houses since the previous safe house. Which should be correct. And with a special case for the first one where you multiply by the number of houses to the first house on the street.
        if (k>0) {
            count = (n-ks[0]+1)*ks[0];
            for(int i=1;i<k;i++) {
                count += (n-ks[i]+1)*(ks[i]-ks[i-1]);
            }
        }
        System.out.println(count);
    }
}

Пример: ввод:

5 2

1

4

Ожидаемый результат:

11

Я кладу его в черный ящик для тестирования, и я сдал первые 10, но получил неправильный ответ на 11-м. Так что я предполагаю, что это какой-то случай, о котором я думаю.

Answer 1

Обратите внимание, что вам не нужно сортировать дома, потому что они уже даны вам в порядке возрастания.

Я решил это на python, и метод, который я использовал, заключался в том, чтобы вычислить для каждого дома первый индекс безопасного дома рядом с ним. Я рассматриваю прогулку к этому первоначальному убежищу как прогулку длиной 1. Затем я складываю количество домов после этого безопасного дома и добавляю это к своему счету.

Например, если N = 5 и k = [3,4,5]. Для каждого дома:

1. (1 -> 3 = 1) + (5 - 3) знак равно 3
2. (2 -> 3 = 1) + (5 - 3) знак равно 3
3. (3 -> 3 = 1) + (5 - 3) знак равно 3
4. (4 -> 4 = 1) + (5 - 4) знак равно 2
5. (5 -> 5 = 1) + (5 - 5) знак равно 1

Дает всего 12