CF2059B.Cost of the Array

普及-

通过率：0%

AC君温馨提醒

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

给定一个数组 $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

样例的第一组数据，只有两种可能的划分： $[[1],[1,1]]$ 和 $[[1,1],[1]]$ 。这两种情况都是 $b_1=1$ 并且 $b_2 \ne 1$ ，所以开销是 $2$ 。

样例的第二组数据，只有一种划分方法，其中 $b=[1,2,3,4,0]$ 。所以开销是 $5$ （ $b_5=0 \ne 5$ ）。

样例的第三组数据，一种划分方案： $[[1],[1,1],[2],[2]]$ 。此时 $b=[1,1,2,0]$ 。这时开销是 $2$ 。