P9228 原神 题解

题目传送门

题目大意

有一个魔法师，她可以用火元素攻击魔法把对附着冰元素的怪物的伤害 \(\times 2\)，用冰元素攻击魔法把对附着火元素的怪物的伤害 \(+5\)。

每个怪物初始时没有附着任何元素，给出冰、火元素对每个怪物的初始伤害，魔法师可以任意安排攻击顺序，求最大总伤害。

解题思路

要求最大总伤害，所以可以把 \(a\) 和 \(b\) 数组从大到小排序，优先用前面的。

因为每个怪物初始时没有附着任何元素，所以要先给每个怪物附着元素，也就是说，每个怪物消耗两个不同的元素，所以最多元素攻击 \(\min(n,m)\) 次。

因为 \(a,b\) 数组已经排好了序，所以可以直接枚举，每次可以在当前的基础上选择 \(+a_i\) 或 \(+k\)，所以可以直接选择 \(\max(a_i,k)\)。即：

最后不要忘记要把初始伤害加上。

代码

AC 记录

#include<bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
ll n,m,k,ans=0;
ll a[1000005],b[1000005];
bool cmp(ll x,ll y){
	return x>y;
}
int main() {
	cin>>n>>m>>k;
	for(ri i=1;i<=n;i++)cin>>a[i];
	for(ri i=1;i<=m;i++)cin>>b[i];
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+m+1,cmp);
	int sum=min(n,m);
	for(ri i=1;i<=sum;i++)
		ans+=max(a[i],k);
	for(ri i=1;i<=n;i++)ans+=a[i];
	for(ri i=1;i<=m;i++)ans+=b[i];
	cout<<ans;
	return 0;
}