A16666. Path Split
编程题
省选/NOI-
知识点
题目描述
给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$。
你需要将 $a$ 划分为若干个子序列 $b_1, b_2, \ldots, b_k$，使得满足以下条件：
- $a$ 中的每个元素恰好属于一个 $b_i$。
- 对于每个序列 $b_i$，设其元素为 $b_{i,1}, b_{i,2}, \ldots, b_{i,p_i}$。对于每一个 $1 \leq j < p_i$，都需满足 $|b_{i,j} - b_{i,j+1}| = 1$。
请计算 $a$ 至少需要划分成几个子序列。
注：“子序列”是指通过从原序列 $a$ 中删除若干（可能为零或全部）元素且不改变其余元素的相对顺序后所得的一个序列。
你需要将 $a$ 划分为若干个子序列 $b_1, b_2, \ldots, b_k$，使得满足以下条件：
- $a$ 中的每个元素恰好属于一个 $b_i$。
- 对于每个序列 $b_i$，设其元素为 $b_{i,1}, b_{i,2}, \ldots, b_{i,p_i}$。对于每一个 $1 \leq j < p_i$，都需满足 $|b_{i,j} - b_{i,j+1}| = 1$。
请计算 $a$ 至少需要划分成几个子序列。
注：“子序列”是指通过从原序列 $a$ 中删除若干（可能为零或全部）元素且不改变其余元素的相对顺序后所得的一个序列。
输入格式
每组测试数据包含若干测试用例。第一行包含整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的组数。
每个测试用例的第一行包含一个整数 $n$（$1\leq n\leq 10^6$），表示序列 $a$ 的长度。
接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\leq a_i\leq 2n$），表示序列 $a$。
保证所有测试用例的 $n$ 之和不超过 $10^6$。
每个测试用例的第一行包含一个整数 $n$（$1\leq n\leq 10^6$），表示序列 $a$ 的长度。
接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\leq a_i\leq 2n$），表示序列 $a$。
保证所有测试用例的 $n$ 之和不超过 $10^6$。
输出格式
对于每个测试用例，输出一个整数，表示将 $a$ 划分成最少多少个子序列。
输入输出样例
输入 #1
7 1 1 1 2 8 11 13 10 11 11 11 13 10 6 8 8 6 7 7 7 3 5 1 3 10 11 14 14 13 12 14 12 10 14 12 1 2
输出 #1
1 1 5 3 3 7 1
说明/提示
在第一个测试用例中，可以将 $a$ 划分为子序列 $[1]$。显然无法划分得更少，因此答案是 $1$。
在第三个测试用例中，可以将 $a$ 划分为子序列 $[11,10,11,10]$、$[13]$、$[11]$、$[11]$、$[13]$。要注意 $[11,10,11,11,11,10]$ 不是一个有效子序列，因为 $|11-11|=0\neq1$。
由 ChatGPT 5 翻译
在第三个测试用例中，可以将 $a$ 划分为子序列 $[11,10,11,10]$、$[13]$、$[11]$、$[11]$、$[13]$。要注意 $[11,10,11,11,11,10]$ 不是一个有效子序列，因为 $|11-11|=0\neq1$。
由 ChatGPT 5 翻译