链接: https://cses.fi/problemset/task/1077

板块: Sliding Window Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个包含 $n$ 个整数的数组。你的任务是，从左到右，对每 $k$ 个元素组成的窗口，计算使所有元素相等的最小总代价。

你可以将每个元素增大或减小，单个元素的代价为 $x$，其中 $x$ 是修改后与原始值的差。总代价为这些代价之和。

输入

第一行包含两个整数 $n$ 和 $k$：元素个数和窗口大小。

接下来有 $n$ 个整数 $x_1,x_2,\ldots,x_n$：数组的内容。

输出

输出 $n-k+1$ 个值：代价。

数据范围

$1 \le k \le n \le 2 \cdot 10^5$ $1 \le x_i \le 10^9$

样例输入

8 3
2 4 3 5 8 1 2 1

样例输出

2 2 5 7 7 1