logoChat01.ai

с++ В игре ДОКА-2 на параметры персонажа не влияют...

作成日: 2025年9月11日

使用モデル GPT-5 by Chat01

質問

с++
В игре ДОКА-2 на параметры персонажа не влияют предметы в инвентаре, а все эффекты являются временными. В данной игре есть два вида эффектов, улучшающих параметры героя: прибавки (прибавляют фиксированное значение к базовой силе героя) и проценты (увеличивают силу героя на некоторый процент от базовой силы героя).

Пусть базовое значение силы героя равно
b
, и вы выбрали некоторые
n
эффектов прибавки с параметрами
d
1
,
d
2
,
…
,
d
n
и
m
эффектов процента с параметрами
p
1
,
p
2
,
…
,
p
m
. Тогда итоговое значение силы равно:

(
b
+
d
1
+
d
2
+
…
+
d
n
)
⋅
100
+
p
1
+
p
2
+
…
+
p
m
100

Обратите внимание, что каждый эффект можно применить не более одного раза.

Вам дано множество доступных эффектов прибавки и множество доступных эффектов процента. Ваша задача — выбрать некоторое количество эффектов, не превосходящее
k
, чтобы получить максимально возможную итоговую силу.

Формат входных данных
Первая строка содержит четыре целых числа
b
,
k
,
x
и
y
(
0
≤
b
,
k
,
x
,
y
≤
50
000
) — базовое значение силы героя, максимальное количество эффектов, которые можно выбрать, количество доступных эффектов прибавки и количество доступных эффектов процента, соответственно.

Вторая строка содержит
x
целых чисел
d
1
,
d
2
,
…
,
d
x
(
0
≤
d
i
≤
50
000
) — параметры эффектов прибавки.

Третья строка содержит
y
целых чисел
p
1
,
p
2
,
…
,
p
y
(
0
≤
p
i
≤
50
000
) — параметры эффектов процента.

Формат выходных данных
В первой строке выведите два целых числа
n
и
m
(
0
≤
n
≤
x
,
0
≤
m
≤
y
,
0
≤
n
+
m
≤
k
) — количество выбранных эффектов прибавки и эффектов процента, соответственно.

Во второй строке выведите
n
целых чисел
i
1
,
i
2
,
…
,
i
n
(
1
≤
i
t
≤
x
) — номера выбранных эффектов прибавки. Все номера должны быть попарно различны.

В третьей строке выведите
m
целых чисел
j
1
,
j
2
,
…
,
j
m
(
1
≤
j
t
≤
y
) — номера выбранных эффектов процента. Все номера должны быть попарно различны.

Эффекты прибавки пронумерованы целыми числами от
1
до
x
в порядке ввода, а эффекты процента пронумерованы целыми числами от
1
до
y
в порядке ввода.

Если существует несколько оптимальных решений, выведите любое из них.

Примеры
Входные данные
10 2 2 2
10 10
10 10
Выходные данные
2 0
2 1

Входные данные
10 3 3 3
5 3 1
20 10 5
Выходные данные
2 1
1 2
1
Примечания
Рассмотрим все варианты эффектов в первом примере:

Если взять оба эффекта прибавки, то сила будет равна
(
10
+
10
+
10
)
⋅
100
100

30

Если взять один эффект прибавки и один эффект процента, то сила будет равна
(
10
+
10
)
⋅
100
+
10
100

22

Если взять оба эффекта процента, то сила будет равна
(
10
)
⋅
100
+
10
+
10
100

12

Таким образом, для максимальной силы необходимо взять два эффекта прибавки.

思考

Considering optimal selection

Okay, we need to choose up to k effects from two lists to maximize the expression (b + sum of d_selected) * (1 + sum of p_selected/100). The key insight is that it's about maximizing the sums of the chosen values. If the numbers are large (up to 50k), my best guess is to pick the top n_a adds and top n_p percents for nondecreasing sums.

Choosing optimal items

The goal is to maximize the product by selecting up to k items from two lists with nonnegative values. Since both types of values (d and p) contribute positively, I should aim to pick the largest values from each list while keeping within the constraints. Essentially, I should focus on choosing the top values, but account for their different roles. Adding zero values doesn’t change the outcome, but it's allowed.

Optimizing list selection

When selecting from two lists, the goal is to pick a combination of up to k items that maximizes the product. If all percentages are zero, for example, it’s better to choose the top adds. If both lists exceed k, I need to find the optimal split to maximize the product, rather than just picking as many as possible.

Optimizing product function

The goal is to maximize the product function f(a, p) = (b + sum of top a adds) * (1 + sum of top p percents). I can compute prefix sums of the sorted adds and percents. To maximize, for a fixed a, pick the highest p values within constraint. Iterating over values of a will help determine the optimal solution.

Thought for 57s

回答

Вот простое оптимальное решение: отсортируем «прибавки» и «проценты» по убыванию, посчитаем их префиксные суммы и переберём, сколько прибавок взять (а), заполняя остаток лимита k лучшими процентами (p = min(k − a, y)). Для каждого (a, p) посчитаем значение (b + sum_d[a]) · (100 + sum_p[p]) и выберем максимум. Затем выведем индексы первых a и p элементов из отсортированных списков.

Код (C++17)

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long b;
    int k, x, y;
    if (!(cin >> b >> k >> x >> y)) return 0;

    vector<long long> dvals(x), pvals(y);
    for (int i = 0; i < x; ++i) cin >> dvals[i];
    for (int i = 0; i < y; ++i) cin >> pvals[i];

    // (значение, исходный индекс)
    vector<pair<long long,int>> adds, pers;
    adds.reserve(x); pers.reserve(y);
    for (int i = 0; i < x; ++i) adds.push_back({dvals[i], i+1});
    for (int i = 0; i < y; ++i) pers.push_back({pvals[i], i+1});

    auto by_desc = [](const auto& a, const auto& b){ return a.first > b.first; };
    sort(adds.begin(), adds.end(), by_desc);
    sort(pers.begin(), pers.end(), by_desc);

    // префиксные суммы
    vector<long long> prefD(x+1, 0), prefP(y+1, 0);
    for (int i = 1; i <= x; ++i) prefD[i] = prefD[i-1] + adds[i-1].first;
    for (int i = 1; i <= y; ++i) prefP[i] = prefP[i-1] + pers[i-1].first;

    long long bestVal = -1;
    int bestA = 0, bestP = 0;

    int maxA = min(k, x);
    for (int a = 0; a <= maxA; ++a) {
        int p = min(k - a, y);
        long long val = (b + prefD[a]) * (100 + prefP[p]);
        if (val > bestVal) {
            bestVal = val;
            bestA = a;
            bestP = p;
        }
    }

    cout << bestA << ' ' << bestP << '\n';
    // индексы выбранных прибавок
    for (int i = 0; i < bestA; ++i) {
        if (i) cout << ' ';
        cout << adds[i].second;
    }
    cout << '\n';
    // индексы выбранных процентов
    for (int i = 0; i < bestP; ++i) {
        if (i) cout << ' ';
        cout << pers[i].second;
    }
    cout << '\n';
    return 0;
}

Почему это корректно

Все di,pi≥0d_i, p_i \ge 0. Для фиксированного количества прибавок aa, итоговая сила монотонно возрастает с ростом суммы процентов, значит выгодно добрать максимум возможных процентов p=min⁡(k−a,y)p = \min(k-a, y). Перебирая aa и используя префиксные суммы отсортированных по убыванию эффектов, мы находим глобальный максимум за O((x+y)log⁡(x+y)+k)O((x+y)\log(x+y) + k).

このQ&Aを共有