[yLOI2023] 苦竹林

Luogu

IDLGP9064

Time1000ms

Memory512MB

DifficultyP2

2023O2优化洛谷月赛

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

Samples

Input #1

5 3
1 2 3 4 5

Output #1

Input #2

6 4
1 7 8 3 4 6

Output #2

API Response (JSON)

{
  "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, \\dot...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments