{"problem":{"name":"[传智杯 #5 初赛] D-莲子的物理热力学","description":{"content":"莲子给定了 $n$ 个整数 $a_1,a_2,\\cdots a_n$，描述每个分子。现在她可以进行**至多** $m$ 次操作（也可以一次也不进行），每次操作可以执行以下两条之一： - 选择 $i$，满足 $a_i=\\min_j\\{a_j\\}$，然后将 $a_i$ 变为 $\\max_j\\{a_j\\}$。 - 选择 $i$，满足 $a_i=\\max_j\\{a_j\\}$，然后将 $a_i$ 变为 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8872"},"statements":[{"statement_type":"Markdown","content":"莲子给定了 $n$ 个整数 $a_1,a_2,\\cdots a_n$，描述每个分子。现在她可以进行**至多** $m$ 次操作（也可以一次也不进行），每次操作可以执行以下两条之一：\n\n- 选择 $i$，满足 $a_i=\\min_j\\{a_j\\}$，然后将 $a_i$ 变为 $\\max_j\\{a_j\\}$。\n- 选择 $i$，满足 $a_i=\\max_j\\{a_j\\}$，然后将 $a_i$ 变为 $\\min_j\\{a_j\\}$。\n\n现在莲子希望需要最小化最终序列的极差（最大值减去最小值的差）。请求出最小的极差。\n\n---\n\n例如，对于序列 $a=\\{5,1,4\\}$，可以进行如下几次操作：\n\n- 选择 $i=1$，满足 $a_1=5$ 是当前的最大值 $5$，可以将 $a_1$ 修改成当前的最小值 $1$，此时序列变成 $\\{1,1,4\\}$；\n- 再选 $i=2$，满足 $a_2=1$ 是当前的最小值 $1$，可以将 $a_2$ 修改成当前的最大值 $4$，此时序列变成 $\\{1,4,4\\}$。 \n\n这两次操作后得到的序列为 $\\{1,4,4\\}$。最大值减去最小值的差为 $|4-1|=3$。\n\n当然，这种操作方式得到的极差并非最小。最优策略是，先将最大值 $a_1=5$ 变成目前的最小值 $1$，再把此时的最大值 $a_3=4$ 变成目前的最小值 $1$。此时序列为 $\\{1,1,1\\}$，得到的极差 $|1-1|=0$ 是所有策略中最小的。\n\n## Input\n\n- 第一行有两个正整数 $n,m$，分别表示序列的长度和你最多可以进行的操作次数。\n- 第二行有 $n$ 个整数 $a$，描述给定的序列。\n\n## Output\n\n- 输出共一行一个整数，表示最优策略下能得到的最小极差。\n\n[samples]\n\n## Background\n\n莲子正在研究分子的运动。\n\n每个分子都有一个速度，约定正方向为正，负方向为负。分子的数量极多，速度又并不一致，看上去杂乱无章。于是莲子希望调整部分分子的速度，使得最终分子们看上去整齐。\n\n## Note\n\n### 样例解释\n\n样例 $1$：$\\{5,1,4\\}\\to\\{1,1,4\\}\\to\\{1,1,1\\}$，极差为 $0$。  \n样例 $2$：$\\{1,2,3,4,5,6,7,8\\}$，什么也做不了，极差为 $7$。  \n样例 $3$：$\\{1,5,5,5,6,6,9,10\\}\\to\\{10,5,5,5,6,6,9,10\\}\\to\\{5,5,5,5,6,6,9,10\\}\\to\\{5,5,5,5,6,6,9,5\\}$，极差为 $4$。\n\n### 数据范围及约定\n\n对于全部数据，保证 $1\\le n \\le 10^5$，$0\\le m\\le10^9$，$|a_i|\\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8872","tags":["贪心","传智杯"],"sample_group":[["3 2\n5 1 4","0"],["8 0\n1 2 3 4 5 6 7 8","7\n"],["8 3\n1 5 5 5 6 6 9 10\n","4\n"]],"created_at":"2026-03-03 11:09:25"}}