Fixed Points

题意翻译

题目描述： 一个整数序列 $a1,a2,...,a_n$，一次操作，可以删除一个数，然后该数右侧的数向左移动一个单位。对于一个长度为 $n$ 的整数序列 $b_i$ ，求最少需要删除几个数后，会有至少 $k$ 个 $i$ 满足 $b_i=i$ 。 输入格式： 第一行一个正整数 $t$ $ (1≤t≤100)$ 表示数据组数。 对于每组数据，第一行两个正整数 $n,k$ 分别表示整数序列的长度，以及至少满足 $b_i=i$ 的个数。 保证 $n$ 在测试数据中的总和不超过 $2000$。 输出格式： 对于每组数据， - 如果无解，输出 $-1$ 。 - 否则，一个整数表示最小的删除次数， 说明/提示： 对于第一个测试数据，序列不满足所需条件，但可以通过删除第一个数来提供，序列为 $[1,2,3,4,5,6]$，有 $6$ 个数满足条件。 对于第二个测试数据，有两种方法：第一种是删除 $a_1$ 和 $a_3$ ；第二种是删除 $a_2$ 和 $a_3$ 。

题目描述

Consider a sequence of integers $ a_1, a_2, \ldots, a_n $ . In one move, you can select any element of the sequence and delete it. After an element is deleted, all elements to the right are shifted to the left by $ 1 $ position, so there are no empty spaces in the sequence. So after you make a move, the sequence's length decreases by $ 1 $ . The indices of the elements after the move are recalculated. E. g. let the sequence be $ a=[3, 2, 2, 1, 5] $ . Let's select the element $ a_3=2 $ in a move. Then after the move the sequence will be equal to $ a=[3, 2, 1, 5] $ , so the $ 3 $ -rd element of the new sequence will be $ a_3=1 $ and the $ 4 $ -th element will be $ a_4=5 $ . You are given a sequence $ a_1, a_2, \ldots, a_n $ and a number $ k $ . You need to find the minimum number of moves you have to make so that in the resulting sequence there will be at least $ k $ elements that are equal to their indices, i. e. the resulting sequence $ b_1, b_2, \ldots, b_m $ will contain at least $ k $ indices $ i $ such that $ b_i = i $ .

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. Then $ t $ test cases follow. Each test case consists of two consecutive lines. The first line contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 2000 $ ). The second line contains a sequence of integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ). The numbers in the sequence are not necessarily different. It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 2000 $ .

输出格式

For each test case output in a single line: - $ -1 $ if there's no desired move sequence; - otherwise, the integer $ x $ ( $ 0 \le x \le n $ ) — the minimum number of the moves to be made so that the resulting sequence will contain at least $ k $ elements that are equal to their indices.

输入输出样例

输入样例 #1

4
7 6
1 1 2 3 4 5 6
5 2
5 1 3 2 3
5 2
5 5 5 5 4
8 4
1 2 3 3 2 2 5 5

输出样例 #1

1
2
-1
2

说明

In the first test case the sequence doesn't satisfy the desired condition, but it can be provided by deleting the first element, hence the sequence will be $ [1, 2, 3, 4, 5, 6] $ and $ 6 $ elements will be equal to their indices. In the second test case there are two ways to get the desired result in $ 2 $ moves: the first one is to delete the $ 1 $ -st and the $ 3 $ -rd elements so that the sequence will be $ [1, 2, 3] $ and have $ 3 $ elements equal to their indices; the second way is to delete the $ 2 $ -nd and the $ 3 $ -rd elements to get the sequence $ [5, 2, 3] $ with $ 2 $ desired elements.

题意翻译

题目描述： 一个整数序列 $a1,a2,...,a_n$，一次操作，可以删除一个数，然后该数右侧的数向左移动一个单位。对于一个长度为 $n$ 的整数序列 $b_i$ ，求最少需要删除几个数后，会有至少 $k$ 个 $i$ 满足 $b_i=i$ 。 输入格式： 第一行一个正整数 $t$ $ (1≤t≤100)$ 表示数据组数。 对于每组数据，第一行两个正整数 $n,k$ 分别表示整数序列的长度，以及至少满足 $b_i=i$ 的个数。 保证 $n$ 在测试数据中的总和不超过 $2000$。 输出格式： 对于每组数据， - 如果无解，输出 $-1$ 。 - 否则，一个整数表示最小的删除次数， 说明/提示： 对于第一个测试数据，序列不满足所需条件，但可以通过删除第一个数来提供，序列为 $[1,2,3,4,5,6]$，有 $6$ 个数满足条件。 对于第二个测试数据，有两种方法：第一种是删除 $a_1$ 和 $a_3$ ；第二种是删除 $a_2$ 和 $a_3$ 。