[蓝桥杯青少年组国赛 2022] 金箍棒

Luogu

IDLGB4298

Time500ms

Memory512MB

DifficultyP3

贪心线段树2022排序蓝桥杯青少年组

淘气的悟空变出了 $N$ 根高度各不相同的金箍棒（$1 \leq $ 高度 $\leq 1000$），并排列成一排。悟空可以对每根金箍棒施法，让金箍棒高度变短或者变长，但每一次施法只能使一根金箍棒变短 $1$ 个高度或者变长 $1$ 个高度。现在悟空想通过施法将 $K$（$K \leq N$）根相邻的金箍棒高度变为相同，且要求施法的次数最少，请你帮助悟空计算出最少需要施法几次可以使 $K$ 根相邻的金箍棒高度变为相同。例如：$N=3$，$K=2$，$3$ 根金箍棒初始高度分别为 $3$、$6$、$1$。 - 第一次对高度为 $3$ 的金箍棒施法变长 $1$ 个高度，变为 $4$； - 第二次对高度为 $6$ 的金箍棒施法变短 $1$ 个高度，变为 $5$； - 第三次对高度为 $4$ 的金箍棒施法变长 $1$ 个高度，变为 $5$； $2$ 根相邻的金箍棒高度变为相同，最少施法 $3$ 次。 ## Input 第一行输入两个正整数 $N$、$K$（$1 \leq K \leq N \leq 10000$），$N$ 表示金箍棒的根数，$K$ 表示需要将 $K$ 根相邻的金箍棒高度变为相同，两个整数之间以一个空格隔开。第二行输入 $N$ 个各不相同的正整数（$1 \leq$ 正整数$\leq 1000$），表示 $N$ 根金箍棒的初始高度，$N$ 个整数之间以一个空格隔开。 ## Output 输出一个整数，表示悟空最少需要施法几次可以使 $K$ 根相邻的金箍棒高度变为相同。 [samples] ## Background 为区分各种时间复杂度的做法，本题时间限制下调到 500 毫秒。

Samples

Input #1

3 2
3 6 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯青少年组国赛 2022] 金箍棒",
    "description": {
      "content": "淘气的悟空变出了 $N$ 根高度各不相同的金箍棒（$1 \\leq $ 高度 $\\leq 1000$），并排列成一排。悟空可以对每根金箍棒施法，让金箍棒高度变短或者变长，但每一次施法只能使一根金箍棒变短 $1$ 个高度或者变长 $1$ 个高度。 现在悟空想通过施法将 $K$（$K \\leq N$）根相邻的金箍棒高度变为相同，且要求施法的次数最少，请你帮助悟空计算出最少需要施法几次可以使 $K$ 根",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4298"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "淘气的悟空变出了 $N$ 根高度各不相同的金箍棒（$1 \\leq $ 高度 $\\leq 1000$），并排列成一排。悟空可以对每根金箍棒施法，让金箍棒高度变短或者变长，但每一次施法只能使一根金箍棒变短 $1$ 个高度或者变长 $1$ 个高度。\n\n现在悟空想通过施法将 $K$（$K \\leq N$）根相邻的金箍棒高度变为相同，且要求施法的次数最少，请你帮助悟空计算出最少需要施法几次可以使 $K$ 根...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments