题解：B4468 符号选择 / opt

Ethan_sun · 2026-01-23 18:58:44 · 题解

B4468 符号选择 / opt

solution

为了使总和最大，显然应该先将正好给到较大的数，再给到小的数。那么我们就将 x 从小到大排个序，只要 x_i 中的 i \le k，sum 就加上 x_i，否则就减去 x_i。

::::error[说句闲话]{open} 这题题目中提到保证 x_1\ge x_2\ge...\ge x_n 好像是错的，通过 assert 发现只有 20\% 的数据满足。

::::

做完了。

AC code

#include <bits/stdc++.h>
#define debug(a) cerr << (#a) << " = " << (a) << endl;
#define int long long
#define maxn 100010
#define endl '\n'
using namespace std;

int n, k, x[maxn];
int solve() {
    int ans = 0;
    sort(x + 1, x + n + 1, greater<int>());
    for (int i = 1; i <= n; i++) {
        if (i <= k) {
            ans += x[i];
        }
        else if (i > k) {
            ans -= x[i];
        }
    }
    return ans;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; t = 1;
    while (t--) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) {
            cin >> x[i];
        }
        cout << solve() << endl;
    }
    return 0;
}