Подсчет чисел больших или равных из 2 списков

@K_Y · Регистрация: 08.01.2024

Студворк — интернет-сервис помощи студентам

Здравствуйте!
Помогите, пожалуйста, оптимизировать решение следующей задачи:
Есть два списка: список заказанных образцов с определённым весом и список весов имеющихся образцов (orders и samples). Необходимо написать программу, подсчитывающую количество выполненных заказов, заказ выполнен, если вес образца равен или выше заказанного.
Я написал следующее решение:

Python
1
2
3
4
5
6
7
8
9
10
11
orders = [int(order) for order in input().split()]
samples = [int(sample) for sample in input().split()]
orders.sort(reverse=True)
count = 0
for order in orders:
    for i in range(len(samples)):
        if samples[i] >= order:
            count += 1
            del samples[i]
            break
print(count)

Данное решение работает, но не проходит по времени выполнения. NymPy использовать нельзя.

Как оптимизировать алгоритм не приходит в голову.

@Gdez · 08.01.2024, 16:24

K_Y, как вариант - вместо внутреннего цикла предварительно отсортировать samples и с помощью bisect_right искать в нем позицию элемента order

@K_Y · 08.01.2024, 16:45 **[ТС]**

Gdez, не совсем понимаю, а как поможет позиция элемента order?

@Aviz__ · 08.01.2024, 16:59

Сообщение от K_Y

а как поможет позиция элемента order?

как сейчас работает твое решение, расскажи нам, пожалуйста?

@Gdez · 08.01.2024, 17:02

K_Y, https://docs-python.ru/standar... ect-right/
Сложность - логарифмическая, вместо O(N)

@K_Y · 08.01.2024, 17:52 **[ТС]**

Сообщение от Aviz__

как сейчас работает твое решение, расскажи нам, пожалуйста?

Начал писать ответ на этот вопрос и в голову пришло решение

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
n = int(input())
orders = [int(order) for order in input().split()]
m = int(input())
samples = [int(sample) for sample in input().split()]
 
orders.sort(reverse=True)
samples.sort(reverse=True)
 
count = 0
iter = 0
 
for order in orders:
    if len(samples) == 0:
        break
    if order > samples[0]:
        continue
    for iter in range(m):
        if order <= samples[iter]:
            count += 1
            del samples[iter]
            break
print(count)

Всем спасибо!

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	08.01.2024, 16:24
	K_Y, как вариант - вместо внутреннего цикла предварительно отсортировать samples и с помощью bisect_right искать в нем позицию элемента order 1

@K_Y 0 / 0 / 0 Регистрация: 08.01.2024 Сообщений: 3
	08.01.2024, 16:45 [ТС]
	Gdez, не совсем понимаю, а как поможет позиция элемента order? 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	08.01.2024, 17:02
	K_Y, https://docs-python.ru/standar... ect-right/ Сложность - логарифмическая, вместо O(N) 1