P9228 原神 题解

· · 题解

原神，启动！（这个题目背景真 nb

很明显，是贪心。玩过原神都知道，只有多打反应，伤害才能尽量高 （冰打火不是 \sout{\times1.5} 吗）。

很容易想出来，打反应的最多次数是 \min(n,m)。我们不妨简化一下题意，火打冰伤害增加 a_i，冰打火伤害增加 k。因为 k 是固定的，所以可以从大到小排序 a_i，看看每个 a_i 和 k 哪个大。每次基础伤害是 a_i+b_i，就是不考虑元素附着的情况下一次火伤和一次冰伤，如果考虑元素附着，那么火打冰会多 a_i 的伤害，冰打火会多 k 的伤害，并且两次伤害打完是没有了元素附着的。根据贪心思想，当然是哪个大选哪个。把所有 \min(n,m) 次反应打完后，剩下的所有可打出的单个元素伤害就可以直接打出去。注意：十年 OI 一场空，不开 long long 见祖宗。

参考代码：（省去了我代码前奇奇怪怪的初始化和万能头）

typedef long long ll;//记得开 long long
int n,m;
ll k,a[1000010],b[1000010],as=0;
bool cmp(ll x,ll y)
{
    return x>y;
}
int main()
{
    ___();//我的初始化函数，可以直接忽略
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>b[i];
    sort(a+1,a+n+1,cmp);//从大到小排序
    int t=min(n,m);//打 min(n,m) 次反应
    for(int i=1;i<=t;i++)
    {
        as+=a[i]>k?a[i]:k;//哪个反应收益高就打那个
        as+=a[i]+b[i];//加上基础的一次火伤和一次冰伤
    }
    //下面两段代码只会执行至多一段，所以不用考虑元素附着
    for(int i=m+1;i<=n;i++)
        as+=a[i];
    for(int i=n+1;i<=m;i++)
        as+=b[i];
    cout<<as<<endl;
    return 0;//完美结束 QwQ
}