@WSGlebKavash

Почему 3 секунд не хватает для выполнения кода?

Условие:
Задача 2.7. Прогнозирование
Ограничение времени: 3 секунды
[Программирование]

Сегодня проходит полуфинал по перетягиванию каната. В нем принимают участие две команды: синих и красных. Обе команды проделали большой путь до этого матча и стремятся к общей цели -− победа на турнире. Всего в полуфинале принимают участие nn человек от каждой команды, и между ними проходит nn матчей. В первом матче канат тянут по одному человеку с каждой стороны, во втором матче канат тянут по два человека с каждой стороны, на третьем - по три человека, и так далее до того, пока канат не будут тянуть с каждой стороны по nn человек. Побеждает в матчах та команда у которой больше суммарная сила на сторону. Если силы равны, объявляется ничья.

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

Исходя из этого, он просит вас написать программу, которая посчитает, какое максимальное количество матчей его команда проиграет при худшем исходе.

Формат входных данных

В первой строке входных данных записано целое число n (1≤n≤2⋅10^5) -− количество участников в каждой команде и, одновременно, количество матчей в финале. Во второй строке записано nn целых чисел ai (1≤a ≤10^9) -− силы участников команды синих. В третьей строке записано n целых чисел bi (1≤b≤10^9) -− силы участников команды красных.

Формат выходных данных

Выведите одно целое число -− максимальное количество матчей, которое команда синих проиграет при худшем исходе.

Пример входных данных
5
2 3 1 4 3
1 2 1 2 2

Пример выходных данных
2

Пояснение к примеру:

Команда синих при худшем исходе проиграет первых два матча. В первом матче они поставят участника с силой 1 против участника команды красных с силой 2. Во втором матче они поставят участников с силой 1 и 2 против участников команды красных с силами 2 и 2. В третьем матче получится ничья. В четвертом и пятом матче команда синих выигрывает.
Я попытался решить задачу с помощью массивов. Я находил минимальные и максимальные значения для каждого раунда и считал сумму сил. Однако код проходит 6 тестов из 17 и выдаёт ошибку: Time limit exceeded.
Как можно оптимизировать код, чтоб он укладывался в 3 секунды?
Код
import copy
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
count = 0;
for i in range(n):
    if i+1 == 1:
        blue = min(a)
        red = max(b)
        if blue < red:
            count += 1
    else:        
        bluelist = copy.deepcopy(a)
        redlist = copy.deepcopy(b)
        blueround = []
        redroud = []
        for j in range(i+1):
            blueround.append(min(bluelist))
            bluelist.remove(min(bluelist))
            redroud.append(max(redlist))
            redlist.remove(max(redlist))
        if sum(blueround) < sum(redroud):
            count += 1
print(count)
  • Вопрос задан
  • 330 просмотров
Решения вопроса 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
У вас решениe за O(n^3), ибо у вас там 2 вложенных цикла до n, а внутри еще и постоянно вызываются min/max, которые проходятся по всему массиву.

Ограничения же в задаче n<10^5. С такими ограничениями максимум O(n log n) решение уложится в 3 секунды.

Подумайте, как его можно изменить, чтобы работало сильно быстрее? Подсказка: сначала вы берете 1 минимальный элемент, потом 2 самых маленьких, потом 3, и т.д. На второй итерации вам уже как бы не надо искать минимум- вы его уже знаете. Вас интересуют только оставшиеся числа. На третьей итерации у вас уже 2 числа раньше найдены. Надо как-то переиспользовать предыдущие вычисления.

Что можно сделать с входным массивом, чтобы можно было получать несколько самых маленьких элементов быстро? Помните, что вам надо уложиться в O(n log n).
Ответ написан
Комментировать
LaRN
@LaRN
Senior Developer
Тут наверное имеет смысл один раз отсортировать bluelist и redlist и далее просто по одному массиву идти с начала, там где нужно брать минимальный элемент, а по второму с конца, там где нужно брать максимальный элемент
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы