{"problem":{"name":"[yLOI2022] 长安幻世绘","description":{"content":"共有 $n$ 个彩灯从左到右排成一排，从左到右用 $1$  到 $n$ 编号，第 $i$ 个彩灯的亮度是 $a_i$。对 $1 \\leq i < n$，我们说 $i$ 号彩灯和 $i + 1$ 号彩灯是相邻的。 我们保证这 $n$ 盏灯的亮度**互不相同**。 一组彩灯的**和谐度**定义为这组彩灯中亮度最大和最小的两盏彩灯的亮度之差。 扶苏想从这 $n$ 个彩灯中选出 $m$ 个**互不相","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9474"},"statements":[{"statement_type":"Markdown","content":"共有 $n$ 个彩灯从左到右排成一排，从左到右用 $1$  到 $n$ 编号，第 $i$ 个彩灯的亮度是 $a_i$。对 $1 \\leq i < n$，我们说 $i$ 号彩灯和 $i + 1$ 号彩灯是相邻的。\n\n我们保证这 $n$ 盏灯的亮度**互不相同**。\n\n一组彩灯的**和谐度**定义为这组彩灯中亮度最大和最小的两盏彩灯的亮度之差。\n\n扶苏想从这 $n$ 个彩灯中选出 $m$ 个**互不相邻**的彩灯作为一组，她希望这组彩灯的和谐度**尽可能小**。请你帮她求出这个最小值。\n\n形式化地，你需要在元素互不相同的数列 $a$ 中选出一个长度为 $m$ 的元素互不相邻的子列，使得子列的极差最小。\n\n## Input\n\n第一行是两个整数，依次表示彩灯的个数 $n$ 和挑出彩灯的个数 $m$。  \n第二行有 $n$ 个整数，第 $i$ 个整数表示彩灯 $i$ 的亮度 $a_i$。\n\n## Output\n\n输出一行一个整数表示答案。\n\n[samples]\n\n## Background\n\n> 长安广月晴，留身影，琵琶行，酒客半醒。  \n> 问你看不清，朱纱帐，翠丝绦，飞天降临。  \n> 美人腰肢半倾璎珞脆，纤手独举琵琶跪，眸眼还生魅。  \n> 麝香抹唇酒更醉，醉灯彩越乱越美。\n\n——银临《长安幻世绘》\n\n## Note\n\n### 样例 1 解释\n\n只能选择第 $1, 3, 5$ 个彩灯。因为其他的选法都会导致有灯相邻。\n\n### 样例 2 解释\n\n可以选择第 $2, 4, 6$ 个彩灯，彩灯的亮度是 $7, 3, 6$，其极差是 $4$。\n\n### 数据规模与约定\n\n- 对 $12\\%$ 的数据，保证 $n \\leq 6$。\n- 对 $36\\%$ 的数据，保证 $n \\leq 100$。\n- 另有 $4\\%$ 的数据，保证 $m = \\lceil\\frac{n}{2}\\rceil$。\n- 另有 $12\\%$ 的数据，保证 $a_i$ 单调递增。\n- 对 $76\\%$ 的数据，保证 $n \\leq 10^3$。\n- 对 $100\\%$ 的数据，保证 $1 \\leq n \\leq 10^5$，$1 \\leq m \\leq \\lceil\\frac{n}{2}\\rceil$，$1 \\leq a_i \\leq 10^9$，$a_i$ 互不相同。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9474","tags":["贪心","线段树","O2优化","排序","洛谷月赛","双指针 two-pointer","动态 DP"],"sample_group":[["5 3\n1 2 3 4 5","4"],["6 3\n1 7 8 3 4 6","4"],["见附加文件中的 D3.in","见附加文件中的 D3.ans"]],"created_at":"2026-03-03 11:09:25"}}