问题描述

给定两组攻击序列：一组为火焰攻击，共 n 次，伤害值分别为 a₁, a₂, ..., aₙ；另一组为冰霜攻击，共 m 次，伤害值分别为 b₁, b₂, ..., bₘ。

元素反应规则如下：

• 每次攻击可以给没有元素附着的怪物附加相应元素，初始状态下怪物无元素附着；
• 当火焰攻击命中冰霜附着的怪物时，本次伤害翻倍（×2），且清除元素附着；
• 当冰霜攻击命中火焰附着的怪物时，本次伤害增加固定值 k（+k），且清除元素附着。

玩家可以任意安排攻击顺序，求能获得的最大总伤害。

输入格式

第一行包含三个整数 n, m, k。
第二行包含 n 个整数，表示火焰攻击的伤害值。
第三行包含 m 个整数，表示冰霜攻击的伤害值。

输出格式

输出一个整数，表示最大总伤害。

样例

输入 #1：

6 7 3
1 1 4 5 1 4
1 9 1 9 8 1 0

输出 #1：67

输入 #2：

5 3 5
1 4 2 8 5
7 1 4

输出 #2：50

问题分析

关键观察

每次元素反应需要一火一冰两组攻击配对。因此，能够触发反应的次数等于 min(n, m)。这是因为每反应一次就会消耗一次火焰攻击和一次冰霜攻击。

当使用火焰攻击触发反应时，有两种增益选择：

• 选择翻倍：额外获得伤害 aᵢ
• 选择+k：额外获得伤害 k

显然，当 aᵢ > k 时，选择翻倍更优；否则选择+k更优。

贪心策略

为了最大化收益，我们应优先让伤害值较大的火焰攻击触发翻倍反应。因此将火焰攻击的伤害值按降序排列，然后依次处理。

设可反应次数为 cnt = min(n, m)，火焰攻击排序后为 c[0] ≥ c[1] ≥ ... ≥ c[n-1]。遍历前 cnt 个火焰攻击：

• 若 c[i] > k，则该次反应选择翻倍，总伤害额外加上 c[i]；
• 否则，该次反应选择+k，总伤害额外加上 k。

最终总伤害 = 所有攻击的基础伤害之和 + 所有反应带来的增益之和。

算法实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    long long k;
    cin >> n >> m >> k;
    
    vector<long long> fire(n);
    vector<long long> ice(m);
    long long total = 0;
    
    for (int i = 0; i < n; i++) {
        cin >> fire[i];
        total += fire[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> ice[i];
        total += ice[i];
    }
    
    sort(fire.begin(), fire.end(), greater<long long>());
    
    int reactionCount = min(n, m);
    long long bonus = 0;
    
    for (int i = 0; i & reactionCount; i++) {
        if (fire[i] > k) {
            bonus += fire[i];
        } else {
            bonus += k;
        }
    }
    
    total += bonus;
    cout << total << '\n';
    
    return 0;
}

复杂度分析

时间复杂度：O(n log n + m)，主要来自排序操作。
空间复杂度：O(n + m)，用于存储两组攻击数据。

正确性证明

设火焰攻击集合为 F = {f₁, f₂, ..., fₙ}，冰霜攻击集合为 I = {i₁, i₂, ..., iₘ}。

引理1：最多进行 min(n, m) 次元素反应。

证明：每次反应需要消耗一次火焰攻击和一次冰霜攻击，因此反应次数不超过火焰攻击次数 n，也不超过冰霜攻击次数 m，即不超过 min(n, m) 次。□

引理2：对于任意一次使用火焰攻击触发的反应，若该火焰伤害值 f > k，则选择翻倍（+f）优于选择+k；若 f ≤ k，则选择+k（+k）优于或等于选择翻倍。

证明：翻倍带来的额外伤害为 f，+k带来的额外伤害为 k。直接比较二者大小即可得证。□

引理3：在确定使用翻倍策略的火焰攻击集合后，应优先选择伤害值较大的火焰攻击执行翻倍。

证明：根据引理2，翻倍增益与火焰伤害值成正相关。交换两次使用翻倍的火焰攻击的位置（设 fₐ ≥ fᵦ），交换前后总增益分别为 fₐ + fᵦ 和 fᵦ + fₐ，两者相等。但若其中一次实际应选择+k（fᵦ ≤ k < fₐ），则将较大的火焰用于翻倍显然更优。□

定理：上述贪心算法得到最优解。

证明：由引理1，反应次数固定为 cnt = min(n, m)。对于前 cnt 个火焰攻击，按引理2确定每个应选择翻倍还是+k。根据引理3，将能产生更大增益的火焰攻击优先用于翻倍，符合最优策略。因此算法得到最大可能总伤害。□