{"problem":{"name":"[厦门小学生 C++ 2024] 战线巡逻","description":{"content":"在一条战线中，有 $n$ 个需要巡逻的点，为了完成巡逻任务，指挥部计划指派 $k$ 个哨兵，每个哨兵可以自由选择起始位置 $i$，不消耗体力。但哨兵每移动一个单位距离（从 $i$ 到 $i+1$ 或 $i-1$），则消耗 $1$ 点体力。 指挥部的目标是将 $k$ 个哨兵合理部署到战线上，使得： - 所有需要巡逻的点都由至少一名哨兵巡逻过。 - 哨兵总体力消耗的最小。 请你设计一个合理的方案，","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":"LGB4179"},"statements":[{"statement_type":"Markdown","content":"在一条战线中，有 $n$ 个需要巡逻的点，为了完成巡逻任务，指挥部计划指派 $k$ 个哨兵，每个哨兵可以自由选择起始位置 $i$，不消耗体力。但哨兵每移动一个单位距离（从 $i$ 到 $i+1$ 或 $i-1$），则消耗 $1$ 点体力。\n\n指挥部的目标是将 $k$ 个哨兵合理部署到战线上，使得：\n- 所有需要巡逻的点都由至少一名哨兵巡逻过。\n- 哨兵总体力消耗的最小。\n\n请你设计一个合理的方案，计算最小的体力消耗，并输出结果。\n\n## Input\n\n- 第一行，两个整数，分别是 $k$ 和 $n$；\n- 第二行，$n$ 个整数，战线中必须巡逻的坐标 $a_i$。\n\n## Output\n\n输出消耗的最少体力。\n\n[samples]\n\n## Background\n\n本试题为 2024 年厦门市小学生 C++ 语言**复赛**试题，数据为洛谷自造。\n\n**初赛**为笔试。\n\n## Note\n\n### 样例解释 1\n\n- 哨兵 1 初始点位即为 $-10$，接下来无需移动，消耗为 $0$。\n- 哨兵 2 初始点位为 $-1$，接下来需向右移动 $2$ 个位置到点位 $1$，消耗为 $2$。\n- 哨兵 3 初始点位即为 $14$，接下来无需移动，消耗为 $0$。\n\n综上，总消耗为 $0+2+0 = 2$。\n\n### 样例解释 2\n\n- 哨兵 1 初始点位即为 $-100$，接下来无需移动，消耗为 0。\n- 哨兵 2 初始点位为 $-11$，接下来无需移动，消耗为 0。\n- 哨兵 3 初始点位即为 $-3$，接下来需向右移动 $3$ 个位置至点位 $0$，消耗为 $3$；接下来需向右移动 $1$ 个位置至点位 $1$，消耗为 $1$；接下来需向右移动 $1$ 个位置至点位 $2$，消耗为 $1$；接下来需向右移动 $7$ 个位置至点位 $9$，消耗为 $7$；共计消耗 $3+1+1+7 = 12$。\n- 哨兵 4 初始点位即为 $17$，接下来需向右移动 $3$ 个位置，消耗为 $3$。\n\n综上，总消耗为 $0+0+12+3 = 15$。\n\n### 样例解释 3\n\n根据题意，哨兵巡逻可以做到不消耗体力。\n\n### 数据范围\n\n对于所有测试数据有：$-10^5 \\leq a_i \\leq 10^5$，$1 \\leq k \\leq 10^5$，$1 \\leq n \\leq 10^5$。\n\n| 测试点 | 特殊性质 A | $k$ | $n$ |\n|:--------:|:------------:|:---:|:---:|\n| $1, 2$   | 否         | $k=1$ | $\\leq 10^5$ |\n| $3, 4$   | 是         | $\\leq 10^5$ | $\\leq 10^5$ |\n| $5, 6, 7$| 否         | $\\leq 10^3$ | $\\leq 10^2$ |\n| $8, 9, 10$ | 否         | $\\leq 10^5$ | $\\leq 10^5$ |\n\n特殊性质 A：保证 $k \\geq n$ 恒成立。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4179","tags":["贪心","2024","福建","排序","差分","科创活动","小学活动"],"sample_group":[["3 4\n-10 -1 1 14","2"],["4 9\n-11 -3 0 9 -100 2 17 20 1","15"],["5 3\n-1000 100 200","0"]],"created_at":"2026-03-03 11:09:25"}}