洛谷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

样例输入 #1

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

样例输出 #1

67

样例 #2

样例输入 #2

5 3 5
1 4 2 8 5
7 1 4

### 样例输出 #2

50

样例 #3

样例输入 #3

1 1 0
2
3

样例输出 #3

7

样例 #4

样例输入 #4

见附件中的 samples/genshin4.in

样例输出 #4

见附件中的 samples/genshin4.ans

样例 #5

样例输入 #5

见附件中的 samples/genshin5.in

样例输出 #5

见附件中的 samples/genshin5.ans

提示

样例 1 解释

攻击采用 $a_1\rightarrow b_4\rightarrow a_2\rightarrow b_3\rightarrow a_5\rightarrow b_5\rightarrow b_7 \rightarrow b_1\rightarrow a_3 \rightarrow b_2\rightarrow a_4\rightarrow b_3 \rightarrow a_6 $，每次的实际伤害为 $1,12,1,4,1,11,0,1,8,9,10,1,8$，总伤害为 $ 67 $。

样例 2 解释

攻击采用 $a_5\rightarrow b_1\rightarrow b_2\rightarrow a_4\rightarrow a_3\rightarrow b_3\rightarrow a_2\rightarrow a_1$，每次的实际伤害为 $5,12,1,16,2,9,4,1$，总伤害为 $50 $。

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n,m \leq 10^6 $，$ 0 \leq a_i,b_i,k \leq 10^9 $。

| 测试点编号 | $n,m \leq$ |特殊性质|

| :----------: | :----------: | :-----------: |

| $1 \sim 5$ | $10$ | |

| $6 \sim 10$ | $1000$ | |

| $11 \sim 12$ | $10 ^6 $ | $k=0$ |

| $13 \sim 14$ | $10 ^6 $ | $k>\max(\max_{i=1}^n\{a_i\},\max_{i=1}^m\{b_i\})$ |

| $15 \sim 16$ | $10 ^6 $ | $n=m$ |

| $17 \sim 25$ | $10 ^6 $ | |

题解

#include <bits/stdc++.h>
#define MIHOMO return 0
using namespace std;

long long n, m, k, ans, kk, minn, a[2000000], b[2000000];
bool cmp(long long a, long long b) {
    return a > b;
}

int main() {
    cin >> n >> m >> k;
    for (long long i = 1; i <= n; i++)
        cin >> a[i], ans += a[i];
    for (long long i = 1; i <= m; i++)
        cin >> b[i], ans += b[i];
    sort(a + 1, a + n + 1, cmp);
    minn = min(n, m);
    for (long long i = 1; i <= minn; i++)
        if (a[i] > k)
            ans += a[i], kk++;
    ans += k * (minn - kk);
    cout << ans << endl;
    MIHOMO;
}