洛谷CF1759B的一种奇妙的解法

一种奇妙的解法

题意

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

思路

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

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

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

代码

#include
#include
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;
}

标签：无