A16570 | $Cost of the Array$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个数组 $a$ 和一个**偶**整数 $k$ （ $2\le k\le n$ ）。你需要将数组 $a$ 分割为恰好 $k$ 个非空子数组。使得数组 $a$ 的每一个元素恰好属于其中一个子数组。 下一步，将所有具有偶数索引的子数组（第 $2$，$4$，…，$k$ 个）连接起来，成为一个新数组 $b$ 。之后，把 $0$ **添加**到数组 $b$ 的末尾。 数组 $b$ 的开销被定义为：最小的使 $b_i\ne i$ 的索引 $i$ 。比如，数组 $b=[1,2,4,5,0]$ 的开销为 $3$ ，因为 $b_1=1$ ， $b_2=2$ ，并且 $b_3\ne 3$。请确定一种划分数组 $a$ 的最优方案，使得数组 $b$ 的开销**最小**。 - 如果 $x$ 是数组 $y$ 的子数组，那么 $x$ 中的所有元素可以通过删除数组 $y$ 的开头几个元素（可能是零个或全部）和末尾几个元素（可能是零个或全部）得到。

**本题有多组测试数据。** 第一行输入一个正整数 $t$（$1\le t\le10^4$） 表示数据组数。每组测试数据的格式如下： 第一行输入两个整数 $n$ 和 $k$ （$2\le k\le n\le 2 \times 10^5$）， $k$ 是偶数。表示数组 $a$ 的长度和子数组数量。 第二行输入 $n$ 个整数 $a_1$ ，$a_2$ ， …， $a_n$ 。表示数组 $a$ 的元素。 保证所有测试数据中 $n$ 的和不超过 $2\times 10^5$ 。

对于每组测试数据，输出一行包含一个整数，表示数组 $b$ 的最小开销。

输入 #1

4
3 2
1 1 1
8 8
1 1 2 2 3 3 4 4
5 4
1 1 1 2 2
5 4
1 1 1000000000 2 2

输出 #1

C++ 编辑器

输入

输出