Подработка

@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 вестимо

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

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

	Подработка 09.10.2020, 14:17. Показов 2230. Ответов 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

Опции темы

Подработка

Решение