P7593 题解

· · 题解

思路

一道简单的数论（？

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

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

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

可以这样理解：

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

接下来让最大的数增加 $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");
        }