经典贪心

题目

本题的意思就是让你先杀死咒语强度小的怪物，它的生命值就是你所需要的时间，然后把杀死怪物的咒语强度加给它相邻的两个怪物，第一个只加给后面，最后一个只加给前面，依次往后直到杀死全部怪物。

本题可以直接贪心，因为到最后每一个怪物的生命值和咒语强度都加了一次，最后一个除外（因为最后一个杀完就结束了），因为是从咒语强度最小的开始，最后一个肯定是咒语强度最大的，所以我们可以直接把所有的值加在一起再减去咒语强度最大的，直接贪心就可以了。

方法一：使用数组存储数据，排序后求最大值

#define ll long long
using namespace std;
const int N=1e5+10;
ll n;
ll a[N*2];
void solve(ll x) {
    ll sum = 0;
    ll y;
    for (int i = 0; i < x; i++) {
        cin >> y;
        sum += y;
    }
    for (int i = 0; i < x; i++) {
        cin >> y;
        a[i] = y;
        sum += y;
    }
    sort(a, a + x);
    cout << sum - a[x - 1] << '\n';
}
int main() {
    ios::sync_with_stdio(0);//使cin cout进行加速，让输入输出速度和scanf和printf差不多
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        solve(n);
    }
    return 0;
}

方法二：不使用数组，降低空间复杂度，再输入的时候就找最大值输入结束，最大值也就找完

#define ll long long
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    ll t;cin>>t;
    while(t--){
        ll ma=0;
        ll n,sum=0,m;cin>>n;
        for(int i=0;i<n;i++){cin>>m;sum+=m;}
        for(int i=0;i<n;i++){
            cin>>m;
            sum+=m;
            if(m>ma)ma=m;
        }
        cout<<sum-ma<<'\n';
    }
    return 0;
}

方法三：时间和空间目前我认为最短的写法

#define ll long long
using namespace std;
void solve(){
    ll ma=0;
    ll n,sum=0,m;cin>>n;
    for(int i=0;i<n;i++){cin>>m;sum+=m;}
    for(int i=0;i<n;i++){
        cin>>m;
        sum+=m;
        if(m>ma)ma=m;
    }
    cout<<sum-ma<<'\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    ll t;cin>>t;
    while(t--)solve();
    return 0;
}