← 返回题目列表

Codeforces · 2152/A

A. 增加或粉碎

中文机器翻译题面 查看原题

Geumjae 有一个由 $$$n$$$ 零组成的数组 $$$a$$$。他的目标是使用最少的操作次数将其转换为给定的目标数组。

他可以任意次数、任意顺序执行以下两种类型的操作:

  1. 增加:选择任意正整数$$$x$$$。增加 全部 数组 $$$a$$$ 的元素由 $$$x$$$ 组成。换句话说,他选择一个正整数 $$$x$$$,并且对于每个 $$$i$$$ ($$$1 \le i \le n$$$),他将 $$$a_i$$$ 替换为 $$$a_i + x$$$。
  2. 粉碎:设置 一些 数组 $$$a$$$ 到 $$$0$$$ 的 元素(可能没有或全部)。换句话说,对于每个$$$i$$$ ($$$1 \le i \le n$$$),他要么用$$$0$$$替换$$$a_i$$$,要么像以前一样保留它。

给定数组 $$$a$$$ 的最终目标状态,找到最小操作总数(两者 增加 和 粉碎) Geumjae 需要表演。

可以证明,对于任何给定的最终数组,操作序列始终存在。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 数组 $$$a$$$ 中的元素数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) — 目标数组 $$$a$$$ 的元素。

输出

对于每个测试用例,输出一个整数 - 所需的最少操作数。

示例

输入
复制

3
3
1 1 3
1
100
9
9 9 3 2 4 4 8 5 3

输出
复制

3
1
11

注意

第一个测试用例的说明:

目标数组是$$$[1, 1, 3]$$$。 3 个操作的可能序列(这是最少的)是:

  1. 最初,数组为 $$$[0, 0, 0]$$$。经过一个 增加 与 $$$x = 2$$$ 进行运算,数组变为 $$$[2, 2, 2]$$$。
  2. 接下来,经过 粉碎 对前两个元素进行操作,数组变为$$$[0, 0, 2]$$$。
  3. 最后,经过 增加 与 $$$x = 1$$$ 的运算,数组变为 $$$[1, 1, 3]$$$。

我们使用了$$$2$$$ 增加 操作和 $$$1$$$ 粉碎 操作总共 $$$3$$$ 操作。

第二个测试用例说明:

目标数组是$$$[100]$$$。单个 增加 与 $$$x = 100$$$ 的运算给出目标数组。