{"problem":{"name":"[yLOI2023] 苦竹林","description":{"content":"共有 $n$ 个风铃悬挂在屋檐下，每个风铃都能发出一定音调的声音。从左到右给风铃从 $1$ 至 $n$ 编号，第 $i$ 个风铃的音调是 $a_i$。 为了表达内心的思念，扶苏决定在 $n$ 个的风铃中取出 $m$ 个，送给远方的朋友。 请你找到最小的整数 $\\varepsilon$，使得存在一种方案，能够从 $n$ 个风铃中挑出 $m$ 个，设挑出风铃的音调为 $b_1, b_2, \\dot","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9064"},"statements":[{"statement_type":"Markdown","content":"共有 $n$ 个风铃悬挂在屋檐下，每个风铃都能发出一定音调的声音。从左到右给风铃从 $1$ 至 $n$ 编号，第 $i$ 个风铃的音调是 $a_i$。\n\n为了表达内心的思念，扶苏决定在 $n$ 个的风铃中取出 $m$ 个，送给远方的朋友。\n\n请你找到最小的整数 $\\varepsilon$，使得存在一种方案，能够从 $n$ 个风铃中挑出 $m$ 个，设挑出风铃的音调为 $b_1, b_2, \\dots b_m$，满足对任意的 $1 \\leq i, j \\leq m$，都有 $|b_i - b_j| \\leq \\varepsilon$。\n\n## Input\n\n第一行是两个整数，表示风铃的个数 $n$ 和挑选出风铃的个数 $m$。  \n第二行有 $n$ 个整数，表示每个风铃的音调。第 $i$ 个整数表示 $a_i$。\n\n## Output\n\n输出一行一个整数，表示最小的 $\\varepsilon$。\n\n[samples]\n\n## Background\n\n> 悬挂在屋檐下的风铃，摇晃的声音很动听。  \n> 思念就像梅雨下不停，我的心境一片泥泞。  \n> 散落在天际里的繁星，闪烁着你我的宿命。  \n> 当枫叶轻盈落入湖心，近看山水一片宁静。  \n\n——银临 & 涵昱《苦竹林》\n\n## Note\n\n### 样例 2 解释\n\n一种选择的方案是选择第 $2,4,5,6$ 四个风铃，音调依次为 $7,3,4,6$。可以得到对任何的 $1 \\leq i, j\\leq 4$，都有 $|b_i - b_j| \\leq 4$。\n\n另一种方案是选择第 $2,3,5,6$ 四个风铃，同样计算得到的 $\\varepsilon$ 为 $4$。\n\n### 数据规模与约定\n\n- 对 $10\\%$ 的数据，$m = 2$。\n- 另有 $10\\%$ 的数据，$m = n$。\n- 对 $40\\%$ 的数据，$n \\leq 5$。\n- 对 $60\\%$ 的数据，保证对所有的 $2 \\leq i \\leq n$，满足 $a_{i - 1} \\leq a_i$，即 $a_i$ 单调不降。\n- 对 $80\\%$ 的数据，$n \\leq 10^3$。\n- 对 $100\\%$ 的数据，$2 \\leq m \\leq n \\leq 10^5$，$1 \\leq a_i \\leq 10^9$。\n\n### 说明\n\n本题共有三个附加样例文件，见题目附件中的 `ring.zip`。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9064","tags":["2023","O2优化","洛谷月赛"],"sample_group":[["5 3\n1 2 3 4 5","2"],["6 4\n1 7 8 3 4 6","4"]],"created_at":"2026-03-03 11:09:25"}}