G5010 [GESP202409 五级] 小杨的武器 题解

知识点：贪心、最值、分类讨论。

解题思路

先找初始武器最大值。多把武器时，把正增益加到最终最强武器，非正增益分配给其他武器；只有一把时必须承担全部增益。

为什么正确

可自由选择强化对象时，正增益集中在最大初值上最优；多余武器可吸收负增益，单武器则没有选择。

易错点

n=1必须累加负值；答案可能为负，最大初值不能初始化为0。

复杂度

时间O(n+m)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    long long best=LLONG_MIN,add=0;
    for(int i=0;i<n;i++) {
        long long x;
        cin>>x;
        best=max(best,x);
    }
    for(int i=0;i<m;i++) {
        long long x;
        cin>>x;
        if(n==1||x>0)add+=x;
    }
    cout<<best+add;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。