Возникла проблема с Каттис, что, как я полагаю, является крайним случаем - PullRequest
Новая
       18

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

0 голосов
/ 21 сентября 2019

Я мог бы помочь с упражнением Каттис Наблюдение за соседством .Я провал на 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

I'mположить его в черный ящик для тестирования, и я прошел первые 10, но на 11-м получил неправильный ответ.Итак, я предполагаю, что это какой-то случай, о котором я думаю.

1 Ответ

0 голосов
/ 21 сентября 2019

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

Я решил это в 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

...