洛谷CF1759B题解
洛谷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;
}