P9228 原神

wuyin331 · 2023-04-22 18:45:04 · 个人记录

题解

这是一道贪心题目。

我们所有技能是全部要使用的，要想其做到最优的话，就是将其增益的数值为最大。

注意到有两种不同的增益：

1. 在冰元素基础上施加火元素，伤害双倍，对结果的增益为 a_i。

2. 在火元素基础上施加冰元素，伤害增加 k 点，对结果的增益为 k。

显然的，最多有 \min\{n,m\} 次增益。

而第一种增益最优为 \max\{a_i\}，第二种固定增益为 k。

那么增益的次数取最优之后，我们每次增益取 \max\{max\{a_i\},k\} 即为全局最优。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[1000005],b;
long long int ans=0;
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),ans+=a[i];
    for(int i=1;i<=m;i++) scanf("%d",&b),ans+=b;
    sort(a+1,a+1+n);
    int pa=n;
    for(int i=1;i<=min(n,m);i++){ 
    if(a[pa]>=k)ans+=a[pa--];
    else ans+=k;
}
    cout<<ans<<endl;
    return 0;
}