题目详情题解（0）讨论（0）提交记录（0）

AT_arc195_d.[ARC195D] Swap and Erase

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

给定一个数列 $ A = (A_1, \ldots, A_N) $。你可以对 $ A $ 进行以下两种操作，顺序和次数不限：

  1. 交换操作：设操作前 $ A $ 的长度为 $ K $。选择满足 $ 1 \leq i \leq K - 1 $ 的整数 $ i $，交换 $ A $ 的第 $ i $ 项和第 $ (i+1) $ 项。
  2. 删除操作：设操作前 $ A $ 的长度为 $ K $。选择满足 $ 1 \leq i \leq K $ 且 $ A $ 的前 $ i $ 项全部相等的整数 $ i $，删除 $ A $ 的前 $ i $ 项。

请求出将 $ A $ 变为空数列所需的最小总操作次数。

给定 $ T $ 个测试用例，请分别求解。

输入格式

输入通过标准输入给出，格式如下：

$ T $
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

每个测试用例的格式为：

$ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

输出格式

对每个测试用例，输出一行答案。

输入输出样例

  • 输入#1

    3
5
1 1 2 1 2
4
4 2 1 3
11
1 2 1 2 1 2 1 2 1 2 1

    输出#1

    3
4
8

说明/提示

约束条件

  • $ 1 \leq T \leq 10^5 $
  • $ 2 \leq N \leq 2 \times 10^5 $
  • $ 1 \leq A_i \leq N $
  • 所有测试用例的 $ N $ 之和不超过 $ 2 \times 10^5 $
  • 输入值均为整数

样例解释 1

对于第一个测试用例，可通过以下 3 次操作清空数列：

  1. 交换第 3 项和第 4 项，得到 $ (1, 1, 1, 2, 2) $。
  2. 删除前 3 项（均为 1），得到 $ (2, 2) $。
  3. 删除前 2 项（均为 2），数列清空。

对于第二个测试用例，只能通过 4 次删除操作（每次删除第 1 项）清空数列，且无法在 3 次或更少操作内完成。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页