用C++作答：# 原神## 题目背景提示：题目背景与题目无关。你说的对但是《原神》是由米哈游自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「提瓦特」的幻想世界在这里被神选中的人将被授予「神之眼」导引元素之力。你将扮演一位名为「旅行者」的神秘角色在自由的旅行中邂逅性格各异、能力独特的同伴们和他们一起击败强敌找回失散的亲人——同时逐步发掘「原神」的真相。因为你的素养很差我现在每天玩原神都能赚

算法1

(贪心) $O(n\log n)$

考虑对于每次攻击，应该选择哪一种元素攻击，才能使得总伤害最大。

首先显然是应该优先选择对于有元素附着的怪物进行攻击，才能利用元素反应带来的额外伤害。

考虑对于每种元素攻击，如果有多个元素附着的怪物，应该先攻击哪一个。可以发现，应该优先攻击元素附着时间较长的怪物，这样才能尽可能利用元素反应。

具体来说，每次攻击时，枚举剩余的攻击次数，找到剩余攻击次数中能造成最大伤害的攻击，更新总伤害，并将元素附着清空。注意，由于每次攻击后都需要重新枚举剩余攻击次数，因此需要使用堆来优化。

时间复杂度

共有 $n+m$ 次攻击，每次攻击需要 $O(\log n+\log m)$ 的时间复杂度，因此总时间复杂度为 $O((n+m)\log(n+m))$。

C++ 代码

算法2

(贪心) $O(n)$

考虑对于每次攻击，应该选择哪一种元素攻击，才能使得总伤害最大。

首先显然是应该优先选择对于有元素附着的怪物进行攻击，才能利用元素反应带来的额外伤害。

考虑对于每种元素攻击，如果有多个元素附着的怪物，应该先攻击哪一个。可以发现，应该优先攻击元素附着时间较长的怪物，这样才能尽可能利用元素反应。

具体来说，每次攻击时，枚举剩余的攻击次数，找到剩余攻击次数中能造成最大伤害的攻击，更新总伤害，并将元素附着清空。

时间复杂度

共有 $n+m$ 次攻击，每次攻击需要 $O(n)$ 的时间复杂度，因此总时间复杂度为 $O((n+m)n)$。

C++ 代