题意

有一个数列是 $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 

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" 

else cout "NO" 

}

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

int n;

cin >> n;

while (n--) {

s();

}

return 0;

}

发送评论编辑评论

题意

思路

代码

发送评论 编辑评论

发送评论编辑评论