#CS1077. 滑动窗口成本

滑动窗口成本

题目背景

翻译自 CSES-1077 题。

题目描述

给定一个包含 n 个正整数的数组，任务是计算每个大小为 k 的滑动窗口内，将所有元素变为相同值的最小总成本。

你可以通过增大或减小每个元素的值来调整它，成本为 x，其中 x 是新值和原值之间的差值。总成本是所有这些差值的和。

输入格式

第一行输入两个整数 n 和 k，分别代表数组的元素个数和滑动窗口的大小。

第二行输入 n 个整数 x1,x2,...,xnx_1, x_2, ..., x_nx1​,x2​,...,xn​，代表数组的值。

输出格式

输出 n−k+1n - k + 1n−k+1 个整数，表示每个滑动窗口内将元素变为相同值的最小总成本。

样例

8 3
2 4 3 5 8 1 2 1

2 2 5 7 7 1

说明/提示

$1 \le k \leq n \le 2\cdot 10^5$

1≤xi≤1091 \leq x_i \le 10^91≤xi​≤109。