洛谷CF1759B的一种奇妙的解法

一种奇妙的解法

题意

有一个数列是 $1 \sim n$ 的一种排列。丢掉了几个数，给出丢掉数的和留着的数，问它们是否能组成这个数列？

思路

我们都知道，求这样公差为 $1$ 的等差数列的和公式是
$$\dfrac{n(n+1)}{2}$$

而根据输入的数据我们可以把数列和求出来，$\times2$ 再平方根即可求出 $n$ ！

最后确保 $n \geq$ 留着的数中最大的数并且用 $n$ 套入上面的公式验证它等于输入的和。

代码

#include<iostream>
#include<cmath>
using namespace std;
void s() {
    int n, tot_lost;
    cin >> n >> tot_lost;
    int maxx = -1;
    int tot_found = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        tot_found += x;
        maxx = max(maxx, x);
    }
    int tot = tot_found + tot_lost;
    int f = sqrt(double(tot * 2));
    int e = f * (f + 1) / 2;
    if (e == tot && f >= maxx) cout << "YES" << endl;
    else cout << "NO" << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {
        s();
    }
    return 0;
}