题目描述

Byteasar loved to play with building blocks as a child.

He used to arrange the blocks into $n$ columns of random height and then organize them in the following manner:

Byteasar would choose a number $k$ and try to arrange the blocks in such a way that some $k$ consecutive columns would be of equal height. Furthermore he always tried to achieve this goal in a minimum number of moves possible, where a single move consists in:

laying one block on top of any column (Byteasar had a huge box with spare blocks, ensuring this move could always be performed), or removing the uppermost block from the top of any column.

However, Byteasar was never quite sure if his sequence of moves was indeed optimal, therefore he has asked you to write a programme that will help him solve the problem.

Task Write a programme that:

reads the number $k$ along with the initial setup of the blocks from the standard input,determines the optimal solution (shortest possible sequence of moves),writes out the solution to the standard output.

输入格式

In the first line of the standard input there are two integers, $n$ and $k$ ($1\le k\le n\le 100\ 000$), separated by a single space.

Each of the following $n$ lines contains the height of some column; the line no. $i+1$ contains the integer $0\le h_i\le 1\ 000\ 000$ - the height of the $i^{th}$ column, ie. the number of blocks it consists of.

输出格式

The optimal solution should be written out to the standard output, ie. such arrangement of blocks that:

contains $k$ consecutive columns of equal height, can be obtained from the initial setup in a minimum possible number of moves.

The output should consist of $n+1$ lines, each one containing a single integer.

The number in the first line should be the minimum number of moves needed to get the desired arrangement.

The line no. $i+1$ (for $1\le i\le n$) should contain the number $h'_i$ - the final height of the $i^{th}$ column.

If more than one optimal solution exists, write out one chosen arbitrarily.

题目大意

题目描述

有 $n$ 柱砖，每柱砖有一个高度，我们现在希望有连续 $k$ 柱的高度是一样的。

你可以选择以下两个动作：

1. 从某柱砖的顶端拿一块砖出来,丢掉不要了。
2. 从仓库中拿出一块砖，放到某一柱，仓库是无限大的。

现在希望用最小次数的动作完成任务，除此之外你还要求输出结束状态时，每柱砖的高度。

输入格式

第一行两个用空格隔开的数表示 $n,k$。

之后 $n$ 行，第 $i+1$ 行一个数表示第 $i$ 柱砖的高度 $h_i$。

输出格式

输出 $n+1$ 行。

第一行一个数表示最小化的答案。

之后 $n$ 行，每行一个数表示结束后每柱砖的高度。

提示

本题 SPJ 的提示说明（按照 SPJ 判断顺序给出）：

Out of Range：输出的数字不在答案可能的范围内。

Wrong Solution：输出方案中不包含连续 $k$ 个相同高度的柱。

Wrong Result：提交的程序的步数和输出方案的步数不相等。

Expected cost = a,found cost = b：期望步数为 $a$，程序的步数为 $b$。

OK!Correct Answer!：答案正确。

5 3
3
9
2
3
1

2
3
9
2
2
2

提示

$1\le k\le n\le 100\ 000$，$0\le h_i\le 1\ 000\ 000$。