题解 CF1759B 【Lost Permutation】

翻译者水一发

先说思路：

既然要求的是从 $1$ 到 $n$ 的合法的排列，那么必定有 $1$ 到 $n$ 的所有数字构成，因此在输入时对数字进行标记，先从 $1$ 补全到 $\max{b_1, ..., b_m}$，若此时已经超过 $sum$ 则为 false; 而如果此时还没有用完，则从 $max + 1$ 开始依次补足，看是否能使得补全数字的和正好等于 $sum$，若超过则 false；反之则为 true。

上代码！

#include <iostream>
#include <cstring>
using namespace std;
int t;
bool flag;
int m, s, mx;
bool vis[5005];
bool check() {
    for (int i = 1; i <= mx; i++) { // 判断有没有补全
        if (!vis[i]) return false;
    }
    return true;
}
void work() {
    int cnt = 0, sum = 0;
    for (int i = 1; ; i++) {
        if (!vis[i]) {
            cnt++; sum += i;
            vis[i] = 1;
        }
        if (sum == s && check()) { // 是否合法 && 是否可行？
            flag = true;
            return ;
        }
        if (sum > s) return ; // 超过则直接 false
    }
}
int main() {
    cin >> t;
    while (t--) {
        cin >> m >> s;
        memset(vis, 0, sizeof(vis));
        flag = 0; mx = 0;
        for (int i = 1; i <= m; i++) {
            int tmp; cin >> tmp;
            mx = max(mx, tmp); // 记最大数
            vis[tmp] = true; // 标记
        }
        work();
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

完结撒花~