[CSP-S 2026] 能量水晶 / crystal（民间数据）

时间限制：1000 ms
内存限制：1024 MiB
满分：100 分
输入输出：标准输入输出。

题目描述

小 R 有 $n$ 颗能量水晶，其中第 $i$ $(1 \le i \le n)$ 颗的能量值为整数 $a_i$。

小 R 想用其中若干颗能量水晶合成一颗大水晶，用于合成的水晶必须具有相同的能量值。小 R 希望参与合成的水晶尽可能多。他可以进行至多 $m$ 次操作。每次操作可以任选一颗水晶，将其能量值增加 $1$；同一颗水晶可以被重复选择。

你需要帮助小 R 求出，进行至多 $m$ 次操作后，他最多能用多少颗能量水晶合成一颗大水晶。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$ 和一个非负整数 $m$，分别表示能量水晶的数量和最多可以进行的操作次数。

输入的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，依次表示每颗能量水晶的能量值。

输出格式

输出到标准输出。

输出一行一个正整数，表示进行至多 $m$ 次操作后，小 R 最多能用多少颗能量水晶合成一颗大水晶。

样例 1

输入：

5 5
1 2 4 8 9

输出：

3

样例 2

输入：

5 8
-3 -1 2 2 7

输出：

4

说明与数据范围

样例 1 解释

小 R 有 $5$ 颗能量水晶，能量值分别为 $1,2,4,8,9$。他可以对能量值为 $1$ 和 $2$ 的水晶分别操作 $3$ 次和 $2$ 次，使原来能量值为 $1,2,4$ 的三颗水晶的能量值都变成 $4$，共进行 $5$ 次操作。因此小 R 可以用 $3$ 颗能量水晶合成一颗大水晶。

样例 3

见题目目录下的 crystal/3.in 与 crystal/3.ans。

该样例满足测试点 $8,9$ 的约束条件。

样例 4

见题目目录下的 crystal/4.in 与 crystal/4.ans。

该样例满足测试点 $10 \sim 12$ 的约束条件。

数据范围

对于所有测试数据，均有：

• $1 \le n \le 5 \times 10^5$，$0 \le m \le 10^{18}$；
• 对于所有 $i$ $(1 \le i \le n)$，均有 $|a_i| \le 10^{12}$。

测试点编号	$n \le$	$m \le$	$\max_{i=1}^{n} \lvert a_i \rvert \le$	特殊性质
$1,2$	$5$	$10$	$20$	无
$3 \sim 5$	$16$	$1000$
$6,7$	$5000$	$10^6$	$100$
$8,9$		$10^9$	$10^5$
$10 \sim 12$	$5 \times 10^5$	$10^8$	$100$
$13 \sim 15$		$10^{18}$	$10^{12}$	A
$16 \sim 18$				B
$19,20$				无

特殊性质 A：对于所有 $i$ $(1 \le i \le n)$，均有 $a_i=i$。

特殊性质 B：$a_1,a_2,\ldots,a_n$ 构成等差数列。

本站提交与数据说明

使用标准输入输出，请去掉 freopen 文件读写。本题采用本站自建民间数据，按原题部分分表的范围、特殊性质及逐点等权分值配置。成绩仅供自测参考，不代表 CCF 官方成绩。

原题样例附件

• crystal.zip

包内附加样例

• 1.ans
• 1.in
• 2.ans
• 2.in
• 3.ans
• 3.in
• 4.ans
• 4.in

来源

xsdoi 比赛 2635 · A 题

题面为本站当前版本，测试数据为本站民间自建数据，成绩不代表 CCF 官方成绩。