洛谷P17331题解

分析

题意

给定一个长度为 $n$ 的数组，每次操作可以选择一个数 $a_i$ 和一个整数 $x$（$0 \le x < a_i$），花费 $x$ 的代价将 $a_i$ 变成 $a_i-x$。求使数组 $\operatorname{mex}$ 为 $k$ 的最小总代价，无法实现则输出 $-1$。

思路

1. 为了使 MEX 为 $k$，则需构造出 $1 \sim k-1$ 且消除 $k$。将数组排序后，用最小的可用数去匹配目标 $t$（从 $1$ 到 $k-1$）。
2. 遍历数组，若 $a_i \ge t$，将其减为 $t$，代价加 $a_i-t$，$t$ 加 $1$。若遍历结束 $t < k$，则无解。
3. 最后遍历剩余元素，若有等于 $k$ 的数，需额外花费 $1$ 的代价将其减小。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
ll a[N];
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
        if (k == 1) {
            if (n > 0 && a[0] == 1) cout << -1 << endl;
            else cout << 0 << endl;
            continue;
        }
        ll ans = 0;
        int t = 1, idx = 0;
        while (idx < n && t < k) {
            if (a[idx] >= t) {
                ans += a[idx] - t;
                t++;
            }
            idx++;
        }
        if (t != k) {
            cout << -1 << endl;
            continue;
        }
        while (idx < n) {
            if (a[idx] == k) ans++;
            idx++;
        }
        cout << ans << endl;
    }
    return 0;
}