Подработка

@Artem0303 · Регистрация: 25.05.2020

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

Виктор решил подработать в течение n дней. Известно, что всего есть m работ, которые он может выполнить. Каждая работа выполняется в течение одного рабочего дня. i-та работа имеет два параметра: a_i
и b_i, которые означают, что, если Виктор выполнит эту работу в день j, то в день j +a _i он получит
b_i рублей.
Он хочет, чтобы в конце n-го дня у него было как можно больше денег. Найдите максимальную
сумму, которую он может иметь.

Формат входных данных
Первая строка содержит два цели числа n и m (1 <= n, m <=10⁵).
Вторая строка содержит m целых чисел a₁, a₂,. . . , a_m (1 <= a_i<=10⁵).
Третья строка содержит m целых чисел b₁, b₂,. . . , b_m (1 <= b_i <=10⁵).

Формат выходных данных
Выведите одно целое число - ответ на задачу.

Пример
standard input________standard output
9 6_________________24
3 6 8 6 5 6___________
5 6 2 1 7 4___________

@eaa · 09.10.2020, 14:19

Жадный алгоритм.

@Olkam · 15.10.2020, 01:02

Можно сделать чтото вроде такого:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
z =[list(t) for t in zip(b, a)]
z.sort()
z.reverse()
d = [0] * n
for i in range(0, m - 1):
    k=z[i][1]
    if k <= n:
        t = n - k
    else:
        continue
    for j in range (0, t):
        if d[(t-1) - j] == 0:
            d[(t-1) - j] = z[i][0]
            break
        else:
            j+=1
print(sum(d))

Хотя я не уверен, как это сработает с очень большими числами...

Интересно, сильно глупо я сделал?

@Olkam · 15.10.2020, 12:36

Никто не подскажет, что можно упростить в данной программе?
Чтобы уменьшить время работы

@eaa · 15.10.2020, 12:41

убрать цикл for j из цикла for i
зачем он там?

@Olkam · 15.10.2020, 13:05

for j - проверка на свободное место в массиве расписания - там диапазон получается, нужно найти, какой из дней не занят

Добавлено через 6 минут
Я не знаю, как еще это сделать

@eaa · 15.10.2020, 13:25

Olkam, ну и какая сложность вашего решения?

@Olkam · 15.10.2020, 13:27

Проблема с индексами k=z[i][1] - при вводе больших чисел (6-7 знаков)

@pancho · 16.10.2020, 15:43

Друзья, использовал ваш код, но при проверке пишет （nameerror:name n is not defined）. Что можно изменить?

@iSmokeJC · 16.10.2020, 16:34

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

Что можно изменить?

Задать переменную n вестимо

Новые блоги и статьи Все статьи Все блоги /
Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .

@Artem0303 0 / 0 / 0 Регистрация: 25.05.2020 Сообщений: 17

	Подработка 09.10.2020, 14:17. Показов 2216. Ответов 9 Метки нет (Все метки) Виктор решил подработать в течение n дней. Известно, что всего есть m работ, которые он может выполнить. Каждая работа выполняется в течение одного рабочего дня. i-та работа имеет два параметра: a_i и b_i, которые означают, что, если Виктор выполнит эту работу в день j, то в день j +a _i он получит b_i рублей. Он хочет, чтобы в конце n-го дня у него было как можно больше денег. Найдите максимальную сумму, которую он может иметь. Формат входных данных Первая строка содержит два цели числа n и m (1 <= n, m <=10⁵). Вторая строка содержит m целых чисел a₁, a₂,. . . , a_m (1 <= a_i<=10⁵). Третья строка содержит m целых чисел b₁, b₂,. . . , b_m (1 <= b_i <=10⁵). Формат выходных данных Выведите одно целое число - ответ на задачу. Пример standard input________standard output 9 6_________________24 3 6 8 6 5 6___________ 5 6 2 1 7 4___________ 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.10.2020, 14:19
	Жадный алгоритм. 0

@Olkam 2 / 1 / 1 Регистрация: 11.10.2020 Сообщений: 8
	15.10.2020, 12:36
	Никто не подскажет, что можно упростить в данной программе? Чтобы уменьшить время работы 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	15.10.2020, 12:41
	убрать цикл for j из цикла for i зачем он там? 0

@Olkam 2 / 1 / 1 Регистрация: 11.10.2020 Сообщений: 8
	15.10.2020, 13:05
	for j - проверка на свободное место в массиве расписания - там диапазон получается, нужно найти, какой из дней не занят Добавлено через 6 минут Я не знаю, как еще это сделать 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	15.10.2020, 13:25
	Olkam, ну и какая сложность вашего решения? 1

@Olkam 2 / 1 / 1 Регистрация: 11.10.2020 Сообщений: 8
	15.10.2020, 13:27
	Проблема с индексами k=z[i][1] - при вводе больших чисел (6-7 знаков) 0

@pancho 0 / 0 / 0 Регистрация: 15.10.2020 Сообщений: 15
	16.10.2020, 15:43
	Друзья, использовал ваш код, но при проверке пишет （nameerror:name n is not defined）. Что можно изменить? 0

Подработка

Решение