自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 22:31:22，当前版本为作者最后更新于2021-05-12 21:44:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

一道简单的数论（？

考虑和最小的情况：选择 $1$ 到 $k$ 之间的所有整数，将这个和记为 $a$。

接下来考虑和最大的情况：选择 $n - k + 1$ 到 $k$ 之间的所有整数，将这个和记为 $b$。

那么在 $1$ 到 $n$ 之间选择 $k$ 个整数，它们的和的上界是 $b$，下界是 $a$。

可以这样理解：

当 $n = 5,k = 3$ 时，选出的数的集合如下：

$\{1,2,3\}$ 此时和为 $6$。

接下来让最大的数增加 $1$，变成 $\{1,2,4\}$，此时和为 $7$。

再让最大的数增加 $1$，变成 $\{1,2,5\}$，此时和为 $8$。

此时最大的数已经无法增加了，那我们让次大的数增加 $1$，此时集合为 $\{1,3,5\}$，和为 $9$。

......

一直这样下去，可以发现在 $[a,b]$ 区间内的整数都可以用在 $[1,n]$ 区间内的不同的 $k$ 个整数的和表示。

接下来就好办了。如果 $s \ge a$ 且 $s \le b$，那么输出 Yes，否则输出 No。

坑点：

• 开 long long
• 没了

求 $\sum\limits_{i=a}^{b}i$ 可以用等差数列公式：$\dfrac{(a + b) \times (b - a + 1)}{2}$

代码

        if (k * (k + 1) / 2 > s || (n + n - k + 1) * k / 2 < s) {
            puts("No");
        } else {
            puts("Yes");
        }