Найти максимально возможную сумму сладости съеденных яблок

@Axaneron · Регистрация: 27.09.2022

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

Всем доброго времени суток!

Решал такую задачку:

Вы любите яблоки и за сегодня хотите съесть x зеленых яблок и y красных. У вас в саду поспело уже a зеленых яблок сладостью p[1], p[2], …, p[a] и b красных яблок сладостью q[1], q[2], …, q[b]. А еще у вас растет c магических яблок сладостью r[1], r[2], …, r[c], которые вы умеете превращать перед едой в красные или зеленые. Понятное дело, что вы хотите съесть яблоки с наибольшей суммарной сладостью. Найдите максимально возможную сумму сладости съеденных яблок, которая может быть достигнута при оптимальном превращении магических яблок.

Формат входных данных:
В первой строке записано пять чисел x, y, a, b, c (1≤x≤a≤10⁵,1≤y≤b≤10⁵,1≤c≤10⁵).

Во второй строке записано a чисел p[i] (1≤p[i]≤10⁹) — сладость зеленых яблок

В третьей строке записано b чисел q[i] (1≤q[i]≤10⁹) — сладость красных яблок

В четвертой строке записано c чисел r[i] (1≤r[i]≤10⁹) сладость магических яблок

Формат выходных данных:
Выведите максимально возможную сумму сладости съеденных яблок.

Примеры:

Входные данные:
1 3 2 3 4
5 6
1 2 3
10 11 12 13

Выходные данные:
46

Входные данные:
1 1 2 2 1
10 4
5 6
1

Выходные данные:
16

Написал для неё код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
 
x, y, a, b, c = map(int, input().split())
g = list(map(int, input().split()))
r = list(map(int, input().split()))
m = list(map(int, input().split()))
m.sort(reverse=True)
 
rg = heapq.nlargest(x, g) + heapq.nlargest(y, r)
rg.sort()
jm = 0
for irg in range(min(x + y, c)):
    if rg[irg] > m[jm]:
        print(sum(rg[irg:]) + sum(m[:jm]))
        quit()
    jm += 1
print(sum(m) + sum(rg[c:]))

Но на 20 тесте неправильный ответ. Помогииите, пожалуйста, люди добрые

P.S. - Кому надо, вот ограничения:

Ограничение времени: 1 с
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Добавлено через 30 минут
Задачу, конечно, не решает, но понял, что второй индекс в моем случае не нужен, просто сначала писал по-другому)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import heapq
 
x, y, a, b, c = map(int, input().split())
g = list(map(int, input().split()))
r = list(map(int, input().split()))
m = list(map(int, input().split()))
m.sort(reverse=True)
 
rg = heapq.nlargest(x, g) + heapq.nlargest(y, r)
rg.sort()
for i in range(min(x + y, c)):
    if rg[i] > m[i]:
        print(sum(rg[i:]) + sum(m[:i]))
        quit()
print(sum(m) + sum(rg[c:]))

Добавлено через 5 минут
Данные тестов, конечно же, неизвестны

@idealist · 31.08.2023, 21:02

Python
1
2
3
4
5
6
7
8
9
x, y, a, b, c = map(int, input('x, y, a, b, c->').split())
p = list(sorted(map(int, input('p->').split()), reverse=True))
q = list(sorted(map(int, input('q->').split()), reverse=True))
r = list(sorted(map(int, input('r->').split()), reverse=True))
real_gr = min(x,a)
real_r = min(y,b)
res = sorted(p[:real_gr] + q[:real_r] + r, reverse=True)
res = res[:min([x+y, real_gr + real_r + c])]
print(sum(res))

@Axaneron · 31.08.2023, 21:18 **[ТС]**

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

x, y, a, b, c = map(int, input('x, y, a, b, c->').split())
p = list(sorted(map(int, input('p->').split()), reverse=True))
q = list(sorted(map(int, input('q->').split()), reverse=True))
r = list(sorted(map(int, input('r->').split()), reverse=True))
real_gr = min(x,a)
real_r = min(y,b)
res = sorted(p[:real_gr] + q[:real_r] + r, reverse=True)
res = res[:min([x+y, real_gr + real_r + c])]
print(sum(res))

Да, это реально сработало. Как работает данный код я понимаю, но почему не работает мой - нет. Не могли бы вы подсказать?

И кстати, 5 и 6 строчки не нужны, так как во входных данных сказано, что a >= x и b >= y

В общем, большое Вам спасибо

Добавлено через 3 минуты
Вот финальная версия кода:

Python
1
2
3
4
5
6
7
x, y, a, b, c = map(int, input().split())
p = list(sorted(map(int, input().split()), reverse=True))
q = list(sorted(map(int, input().split()), reverse=True))
r = list(sorted(map(int, input().split()), reverse=True))
res = sorted(p[:x] + q[:y] + r, reverse=True)
res = res[:x + y]
print(sum(res))

@idealist · 31.08.2023, 21:26

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

5 и 6 строчки не нужны, так как во входных данных сказано, что a >= x и b >= y

Пардон, не заметил. Ну, тогда все еще проще!

Добавлено через 4 минуты

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

Как работает данный код я понимаю, но почему не работает мой - нет. Не могли бы вы подсказать?

Ну, если вы сами не понимаете свой код, то мне и подавно не понять!))
А если серьезно, то у вас там так сложно, что я даже вчитываться не стал. Что-то вы там перемудрили!

@Axaneron · 31.08.2023, 21:48 **[ТС]**

Я пока ответа ждал, сам решил задачу все же, через словари) Кстати, решение неплохое, пускай и не самое лучшее

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
apples = {}
for array, key, length in [(g, 'g', a), (r, 'r', b), (m, 'm', c)]:
    for i in range(length):
        apples[f'{key}{i}'] = array[i]
apples = dict(sorted(apples.items(), key=lambda item: item[1], reverse=True))
g_counter = 0
r_counter = 0
m_counter = 0
g_sum = 0
r_sum = 0
m_sum = 0
for key in apples:
    if (g_counter + r_counter + m_counter) == x + y:
        print(g_sum + r_sum + m_sum)
        quit()
    apple_type = key[0]
    sweetness = apples[key]
    if apple_type == 'g':
        if g_counter == x:
            continue
        g_counter += 1
        g_sum += sweetness
        continue
    if apple_type == 'r':
        if r_counter == y:
            continue
        r_counter += 1
        r_sum += sweetness
        continue
    m_counter += 1
    m_sum += sweetness

Так что все же могу считать, что решил сам

@idealist · 31.08.2023, 22:02

Axaneron, один умный человек сказал, что программирование - это управление сложностью. А когда вы программируете - еще непонятно - то ли вы управляете сложностью, то ли она управляет вами))

@DOPIXKMNLD · 01.09.2023, 08:05

Это задание текущей олимпиады, жб

Добавлено через 40 секунд
Ошибка - выкладывать это сюда, человек 200 украдет твое решение и по итогу у тебя его отключат за плагиат

Новые блоги и статьи Все статьи Все блоги /
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, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@idealist 3750 / 1944 / 612 Регистрация: 21.11.2021 Сообщений: 3,706
	31.08.2023, 22:02
	Axaneron, один умный человек сказал, что программирование - это управление сложностью. А когда вы программируете - еще непонятно - то ли вы управляете сложностью, то ли она управляет вами)) 0

@DOPIXKMNLD Йуный плагиат-падаван) 176 / 119 / 45 Регистрация: 17.10.2022 Сообщений: 566
	01.09.2023, 08:05
	Это задание текущей олимпиады, жб Добавлено через 40 секунд Ошибка - выкладывать это сюда, человек 200 украдет твое решение и по итогу у тебя его отключат за плагиат 0

Найти максимально возможную сумму сладости съеденных яблок

Решение