CF1773L.Lisa's Sequences

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Lisa 喜欢玩整数序列。当她得到一个长度为 $n$ 的新整数序列 $a_i$ 时，她会开始寻找所有的单调子序列。一个单调子序列 $[l, r]$ 由两个下标 $l$ 和 $r$ （ $1 \le l < r \le n$ ）定义，满足以下两种情况之一：

对于所有 $i = l, l+1, \ldots, r-1$ ，都有 $a_i \le a_{i+1}$ ；
对于所有 $i = l, l+1, \ldots, r-1$ ，都有 $a_i \ge a_{i+1}$ 。

如果存在一个长度恰好等于她的无聊阈值 $k$ 的单调子序列 $[l, r]$ ，即 $r - l + 1 = k$ ，Lisa 就会觉得序列 $a_i$ 很无聊。

Lucas 有一个序列 $b_i$ ，他想把它展示给 Lisa，但这个序列可能会让 Lisa 感到无聊。因此，他想修改序列 $b_i$ 的一些元素，使得 Lisa 不会觉得无聊。然而，Lucas 很懒，他希望修改 $b_i$ 的元素数量尽可能少。你的任务是帮助 Lucas 找到需要修改的最少元素数目。

输入格式

第一行包含两个整数 $n$ 和 $k$ （ $3 \le k \le n \le 10^6$ ），分别表示序列的长度和 Lisa 的无聊阈值。第二行包含 $n$ 个整数 $b_i$ （ $1 \le b_i \le 99\,999$ ），表示 Lucas 原有的序列。

输出格式

第一行输出一个整数 $m$ ，表示需要修改 $b_i$ 的最小元素数量，使得序列对 Lisa 来说不再无聊。第二行输出 $n$ 个整数 $a_i$ （ $0 \le a_i \le 100\,000$ ），表示修改后的序列，且 $a_i$ 与原序列 $b_i$ 恰好有 $m$ 个位置不同，并且对 Lisa 来说不无聊。

输入输出样例

输入#1
```
5 3
1 2 3 4 5
```
输出#1
```
2
1 0 3 0 5
```
输入#2
```
6 3
1 1 1 1 1 1
```
输出#2
```
3
1 100000 0 1 0 1
```
输入#3
```
6 4
1 1 4 4 1 1
```
输出#3
```
1
1 1 4 0 1 1
```
输入#4
```
6 4
4 4 4 2 2 2
```
输出#4
```
2
4 4 0 2 0 2
```
输入#5
```
6 4
4 4 4 3 4 4
```
输出#5
```
1
4 4 100000 3 4 4
```
输入#6
```
8 4
2 1 1 3 3 1 1 2
```
输出#6
```
2
2 1 1 3 0 1 0 2
```

输入#7

10 4
1 1 1 2 2 1 1 2 2 1

输出#7

2
1 1 100000 2 2 100000 1 2 2 1

输入#8
```
7 5
5 4 4 3 4 4 4
```
输出#8
```
0
5 4 4 3 4 4 4
```

输入#9

10 10
1 1 1 1 1 1 1 1 1 1

输出#9

1
1 1 1 1 1 1 1 1 0 1

说明/提示

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页