题解 | AOE还是单体？

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using vi = vector<int>;
void solve() {
    int n, x;cin >> n >> x;
    vi a(n);
    for (int i = 0;i < n;i++) {
        cin >> a[i];
    }
    int ans = 1e18;
    sort(rall(a));
    int sum = 0;
    for (int i = 0;i < n;i++) {
        ans = min(ans, a[i] * x + sum - i * a[i]);
        sum += a[i];
    }
    cout << min(sum, ans) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "----Test " << i << "----" << endl;
        solve();
    }
    return 0;
}

先降序排列，枚举删除之前遍历所有数都到当前数需要消耗的贡献，再加上当前数*x的贡献，就是全部数删除到小于等于当前数再aoe的贡献，找最小值，注意删全部也是一种解，考虑前缀和优化如上面代码