洛谷P9228 原神 题解

题目链接：P9228 原神

题意：

原神中有一个魔法师，她可以打出 $ n $ 次火元素攻击魔法和 $ m $ 次冰元素攻击魔法，每次攻击的伤害分别为 $ a_1,a_2,\cdots, a_n $ 和 $ b_1,b_2,\cdots, b_m $。

元素攻击之间存在如下反应规则：

• 每次元素攻击可以给没有元素附着的怪物附着相应的元素，初始时怪物没有元素附着；

• 如果用火元素攻击打到冰元素附着的怪物身上，那么本次伤害将 $ \times 2 $，并清空元素附着；

• 如果用冰元素攻击打到火元素附着的怪物身上，那么本次伤害将 $ +k $，并清空元素附着。

现在魔法师可以任意安排攻击顺序，也就是说，每次攻击过后，魔法师可以从自己没有使用过的魔法中任意挑选一种使用。她希望最大化总伤害，请问最大总伤害是多少。

输入格式：

第一行三个整数 $ n,m,k $。

第二行 $ n $ 个整数 $ a_1,a_2,\cdots, a_n $。

第三行 $ m $ 个整数 $ b_1,b_2,\cdots, b_m $。

输出格式：

一行一个整数，表示答案。

数据范围：

$1 \leq n,m \leq 10^6$，$0 \leq a_i,b_i,k \leq 10^9$

注意到每次攻击通常是由一个火魔法加一个冰魔法组合而成的。

显然冰魔法的攻击不会影响到总伤害，而火魔法在小于 $k$ 时没有必要进行翻倍操作。

那么问题就很简单了，如果 $n \le m$ ，我们枚举每个火魔法 $a_i$ ，贡献为

$$a_i + \max\{a_i, k\}$$

接着加上所有的 $b_i$ 即可。

反之，若 $n > m$ ，这意味着有些火魔法无法配对，那么我们就优先将 $a_i$ 较大的进行配对。

时间复杂度 $\mathcal{O}(n\log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))

int n,m,k,ans,a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> k;
    if(n <= m)
    {
        for(int i = 1, x; i <= n; i++) { cin >> x; ans += x + max(x, k); }
        for(int i = 1, x; i <= m; i++) { cin >> x; ans += x; }
    }else
    {
        for(int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + 1 + n, greater<int>());
        for(int i = 1; i <= m; i++) ans += a[i] + max(a[i], k);
        for(int i = m + 1; i <= n; i++) ans += a[i];
        for(int i = 1, x; i <= m; i++) { cin >> x; ans += x; }
    }
    cout << ans << '\n';
    return 0;
}

---

题外话：

圆神，启动！