A2462. KLO-Building blocks
编程题
提高+/省选-
知识点
题目描述
有 $n$ 柱砖，每柱砖有一个高度，我们现在希望有连续 $k$ 柱的高度是一样的。
你可以选择以下两个动作：
1. 从某柱砖的顶端拿一块砖出来,丢掉不要了。
2. 从仓库中拿出一块砖，放到某一柱，仓库是无限大的。
现在希望用最小次数的动作完成任务，除此之外你还要求输出结束状态时，每柱砖的高度。
你可以选择以下两个动作：
1. 从某柱砖的顶端拿一块砖出来,丢掉不要了。
2. 从仓库中拿出一块砖，放到某一柱，仓库是无限大的。
现在希望用最小次数的动作完成任务，除此之外你还要求输出结束状态时，每柱砖的高度。
输入格式
第一行两个用空格隔开的数表示 $n,k$。
之后 $n$ 行，第 $i+1$ 行一个数表示第 $i$ 柱砖的高度 $h_i$。
之后 $n$ 行，第 $i+1$ 行一个数表示第 $i$ 柱砖的高度 $h_i$。
输出格式
输出 $n+1$ 行。
第一行一个数表示最小化的答案。
之后 $n$ 行，每行一个数表示结束后每柱砖的高度。
第一行一个数表示最小化的答案。
之后 $n$ 行，每行一个数表示结束后每柱砖的高度。
输入输出样例
输入 #1
5 3 3 9 2 3 1
输出 #1
2 3 9 2 2 2
说明/提示
$1\le k\le n\le 100\ 000$，$0\le h_i\le 1\ 000\ 000$。
本题SPJ的提示说明（按照SPJ判断顺序给出）：
本题SPJ的提示说明（按照SPJ判断顺序给出）：
Out of Range：输出的数字不在答案可能的范围内。Wrong Solution：输出方案中不包含连续k个相同高度的柱。Wrong Result：提交的程序的步数和输出方案的步数不相等。Expected cost = a,found cost = b：期望步数为 $a$，程序的步数为 $b$。OK!Correct Answer!：答案正确。