Тест памяти для солдат

Я решаю следующую проблему для шеф-повара :

  

\ $ N \ $ Солдаты выстроились в очередь для теста памяти. Они пронумерованы от 0 до N-1 слева направо.
  В тесте есть \ $ M \ $ раунды. В каждом раунде Капитан выбирает одну позицию. Солдат в этом положении будет пронумерован 0. Все солдаты справа от выбранной позиции будут пронумерованы на один больше, чем солдат слева от него. Все солдаты слева от выбранного места будут пронумерованы на один больше, чем солдат справа от него.   например. если \ $ N = 6 \ $, а выбранная позиция равна 3, , то нумерация будет \ $ [3, 2, 1, 0, 1, 2] \ $ .

     

После раундов \ $ M \ $ капитан попросил каждого солдата выкрикнуть наибольшее число, которое ему было присвоено во время раундов \ $ M \ $. Чтобы проверить правильность, капитан попросил вас привести правильные значения для каждого солдата (это правильное значение, которое должен вызвать каждый солдат).

     

Ввод
  - Первая строка ввода содержит целое число \ $ T \ $, обозначающее количество тестовых случаев.
  - Первая строка каждого тестового примера содержит два целых числа, \ $ N \ $ и \ $ M \ $
  - Вторая строка каждого тестового примера содержит \ $ M \ $ целые числа, позиции, выбранные капитаном, в этом порядке.

     

Выход
  Для каждого тестового примера выведите одну строку с целыми числами \ $ N \ $.

     

Ограничения:
  \ $ 1 ≤ T ≤ 10 ^ 4 \ $
  \ $ 1 ≤ N ≤ 10 ^ 5 \ $
  \ $ 1 ≤ M ≤ 10 ^ 5 \ $
  \ $ 1 ≤ \ sum {N} ≤ 10 ^ 5 \ $
  \ $ 1 ≤ \ sum {M} ≤ 10 ^ 5 \ $
  \ $ 0 ≤ {Позиции \ selected \ by \ captain} ≤ N-1 \ $

     

Пример

     

Ввод

2
4 1
1
6 2
2 3
     

Выход

1 0 1 2
3 2 1 1 2 3

Я решил проблему с использованием Java, и мой код отлично работает на моем ПК, но, к сожалению, я получаю Time Limit Exceeded для этого кода:

import java.io.*;
class ANUARM{
  public static void main(String[] s) throws Exception{
  BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
  int testCases = Integer.parseInt(input.readLine());
  for(int i = 0 ; i < testCases ; ++i){
     String[] num = input.readLine().split(" ");
     int n = Integer.parseInt(num[0]);
     int m = Integer.parseInt(num[1]);
     int[] array = new int[n];
     String[] pos = input.readLine().split(" ");
     for(int j = 0 ; j<m ; ++j){
      int temp = Integer.parseInt(pos[j]);
      for(int k = 0 ; k<n ; ++k){
       int posAquired = temp - k;
        if(k > temp)
         posAquired = k-temp;
         if(posAquired > array[k])
          array[k] = posAquired;
      }
     }
     for(int a : array){
      System.out.print(a+" ");
     }
     System.out.println();
    }
  }
}

Сначала я использовал Scanner, но я видел в FAQ, что Scanner работает медленно, поэтому я использовал BufferedReader НО все же я получаю TLE. Может ли кто-нибудь сказать мне, где я могу оптимизировать свой код, а также оптимизировать? »

11 голосов | спросил Nawed Shaikh 20 +04002014-10-20T12:42:18+04:00312014bEurope/MoscowMon, 20 Oct 2014 12:42:18 +0400 2014, 12:42:18

1 ответ


10

Scanner медленнее по сравнению с BufferedReader но это не главное узкое место этого кода. (Скорость разбора входных данных вряд ли будет узким местом в конкурсах программирования.)

Основным узким местом является то, что для каждой позиции выкрикивается, вы перебираете каждого солдата. Чем больше позиций выкрикивается, тем более расточительным это становится.

Поймите, что капитан мог выкрикивать миллион позиций, но все, что имеет значение, - это минимальные и максимальные позиции. Скажем, есть 7 солдат, и капитан выкрикивает 1000 чисел, но всегда между 3 или 4:

  

0 1 2 {3 4} 5 6

Независимо от того, сколько чисел он закричал, наибольшее количество солдат, назначенных солдатам, будет:

  

4 3 2 {1 1} 2 3

Эта логика упростит алгоритм:

  • Найдите min и max номер, крикнул капитан
  • Идите по солдатам (всего один проход!) и назначьте самый большой из \ $ | i - max | \ $ и \ $ | i - min | \ $

Простая реализация на Java, учитывая количество солдат и позиции, выкрикиваемые капитаном:

private int[] solution(int num, int... positions) {
    int[] soldiers = new int[num];
    int max = 0;
    int min = num - 1;
    for (int pos : positions) {
        min = Math.min(min, pos);
        max = Math.max(max, pos);
    }
    for (int i = 0; i < soldiers.length; ++i) {
        soldiers[i] = Math.max(Math.abs(i - max), Math.abs(i - min));
    }
    return soldiers;
}

Единичные тесты:

@Test
public void testBasic1() {
    assertArrayEquals(new int[]{1, 0, 1, 2}, solution(4, 1));
}

@Test
public void testBasic2() {
    assertArrayEquals(new int[]{3, 2, 1, 1, 2, 3}, solution(6, 2, 3));
}

И последнее, но не менее важное: исходный код был плохо отформатирован и не был хорошо разложен на методы. Лучше всего разделить синтаксический анализ и основную логику, увидеть более четкие, чтобы вы могли лучше сосредоточиться на основной реализации. Разделение синтаксического анализа и основной логики иногда жертвует некоторой производительностью или требует большего объема памяти, но по моему опыту никогда не хватало времени /памяти. При написании чистым способом вы эффективно получаете больше времени кодирования, чтобы сосредоточиться на реальной проблеме, и найти трюк для оптимизации алгоритма.

ответил janos 20 +04002014-10-20T14:25:20+04:00312014bEurope/MoscowMon, 20 Oct 2014 14:25:20 +0400 2014, 14:25:20

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132