logo AlgoBeat OnlineJudge
登录 注册

#215918. 【MX-X26-T2】「Cfz Round 7」Tap Tap Dance

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

羅針盤の指す方角は / 指南针所指的

心が望むもの / 便是心之所向


Yuki 有一个长度为 的序列

Yuki 定义一次「鱼鱼」操作为:

  • 选择两个整数 ,满足
  • ,删除 中大于 的数,并将 修改为此时序列 的长度。

你需要求出使序列 尽可能短所需的「鱼鱼」操作次数的最小值。

本题中,一个序列的 为该序列中未出现过的最小非负整数,例如:

特别地,当序列为空时,该序列的

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 ,分别表示该测试点所属的子任务编号和测试数据组数。样例满足

接下来依次输入每组测试数据。对于每组测试数据:

  • 第一行包含一个整数
  • 第二行包含 个整数

输出格式

对于每组测试数据,输出一行,包含一个整数,表示使序列 尽可能短所需的「鱼鱼」操作次数的最小值。

样例

样例输入 1

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

样例输出 1

1
2
1
3
2

数据范围与提示

样例 1 解释

对于第 组测试数据,直接选择 进行「鱼鱼」操作即可使序列 变成 。容易证明 无法被删除,此时序列 的长度达到最小值。

对于第 组测试数据,可以先选择 进行「鱼鱼」操作,此时序列 变为 ,再选择 进行「鱼鱼」操作,此时序列 变成 ,长度达到最小值。

数据范围

表示单个测试点中 的和。

对于所有测试数据,均有:

  • 对于所有 ,均有

本题采用捆绑测试。

  • Subtask 1(18 points):
  • Subtask 2(5 points):保证序列 中不存在
  • Subtask 3(21 points):保证序列 中存在恰好一个
  • Subtask 4(24 points):对于所有不大于 的正奇数 ,保证
  • Subtask 5(32 points):无特殊限制。