#CF2266H. Deque Malfunction
Deque Malfunction
题目描述
Vihaan 自己实现了一个双端队列(deque),但它有时会发生故障。
Vihaan 希望最终双端队列中的内容从前到后为 。
给定一个长度为 的数组 。元素按 的顺序依次到达。
每当一个元素 到达时,Vihaan 必须执行以下操作之一:
- 将 推入双端队列的 front(前端)。
- 将 推入双端队列的 back(后端)。
- 让双端队列发生故障,将 插入到双端队列中任意他选择的位置。
此外,Vihaan 还可以在任意时刻执行以下操作之一:
- 移除双端队列 front(前端)的元素。
- 移除双端队列 back(后端)的元素。
在所有 个元素都到达并且所有操作都执行完毕后,双端队列必须恰好包含 ,且顺序一致。
求使得双端队列发生故障的最少次数,以得到 ;若不可能,则判定为不可能。
输入格式
第一行包含一个整数 ()—测试用例的数量。
每个测试用例的第一行包含两个整数 和 ()—目标双端队列的长度和到达元素的数量。
第二行包含 个整数 ()—元素到达的顺序。
保证所有测试用例中 的总和不超过 。
输出格式
对于每个测试用例,输出一个整数—双端队列必须发生故障的最少次数。
如果无法得到目标双端队列,输出 。
样例
9
1 3
1 1 1
3 4
2 1 1 2
4 4
1 4 2 3
4 5
4 3 4 2 1
5 8
1 3 2 5 4 3 1 2
6 6
1 6 5 4 3 2
4 6
1 3 2 3 4 3
6 8
2 6 3 5 2 1 4 2
6 8
1 6 2 5 1 5 3 4
0
-1
2
0
1
4
0
2
3
说明
在第一个测试用例中,Vihaan 可以执行以下操作:
- 将第一个 推入前端:
然后,立即将其弹出:
- 将第二个 推入前端:
然后,立即将其弹出:
- 将最后一个 推入后端:
因此,不需要任何故障操作。
在第二个测试用例中,值 从未在 中出现,因此不可能得到目标双端队列。
在第三个测试用例中,Vihaan 可以执行以下操作:
- 将 推入后端:
- 将 推入后端:
- 让双端队列发生故障,并将 插入到 和 之间:
- 让双端队列发生故障,并将 插入到 和 之间:
可以证明,使用少于 2 次故障操作的任何操作序列都无法得到目标双端队列。因此,最小值为 2。
在第四个测试用例中,Vihaan 可以执行以下操作:
- 将第一次出现的 推入前端:
然后,立即将其弹出:
- 将 推入后端:
- 将第二次出现的 推入后端:
- 将 推入前端:
- 将 推入前端:
因此,不需要任何故障操作。
来源
导入自 Codeforces — Codeforces Round 1122 (Div. 3)。