310167: CF1792A. GamingForces
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
GamingForces
题意翻译
### 题目背景 Monocarp 正在玩电脑游戏。他打算杀死 $n$ 个怪兽，第 $i$ 个的血量为 $h_i$。 Monocarp 的角色有两个魔法咒语如下，都可以以任意顺序用任意次（可以不用），每次使用相当于一次操作。 1. 选择两个怪兽并**各**扣一滴血。 2. 选择一个怪兽并且直接杀死。 当一个怪兽血量为 $0$ 时，**他死了**。 求杀死所有怪兽的最少操作次数。 ### 输入 第一行一个整数 $t(1\le t\le 10^4)$ 表示数据组数。 对于每一组数据： 第一行一个整数 $n(1\le n\le 100)$ 表示怪兽数量。 第二行 $n$ 个整数 $h_1,h_2,...,h_n(1\le h_i\le 100)$ 表示每个怪兽的血量。 另外保证 $\sum n\le 2\times10^4$。 ### 输出 对于每组数据，一个数表示最少操作次数，具体见题意部分。题目描述
Monocarp is playing a computer game. He's going to kill $ n $ monsters, the $ i $ -th of them has $ h_i $ health. Monocarp's character has two spells, either of which he can cast an arbitrary number of times (possibly, zero) and in an arbitrary order: - choose exactly two alive monsters and decrease their health by $ 1 $ ; - choose a single monster and kill it. When a monster's health becomes $ 0 $ , it dies. What's the minimum number of spell casts Monocarp should perform in order to kill all monsters?输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains a single integer $ n $ ( $ 1 \le n \le 100 $ ) — the number of monsters. The second line contains $ n $ integers $ h_1, h_2, \dots, h_n $ ( $ 1 \le h_i \le 100 $ ) — the health of each monster. The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^4 $ .
输出格式
For each testcase, print a single integer — the minimum number of spell casts Monocarp should perform in order to kill all monsters.
输入输出样例
输入样例 #1
3
4
1 2 1 2
3
2 4 2
5
1 2 3 4 5输出样例 #1
3
3
5说明
In the first testcase, the initial health list is $ [1, 2, 1, 2] $ . Three spells are casted: - the first spell on monsters $ 1 $ and $ 2 $ — monster $ 1 $ dies, monster $ 2 $ has now health $ 1 $ , new health list is $ [0, 1, 1, 2] $ ; - the first spell on monsters $ 3 $ and $ 4 $ — monster $ 3 $ dies, monster $ 4 $ has now health $ 1 $ , new health list is $ [0, 1, 0, 1] $ ; - the first spell on monsters $ 2 $ and $ 4 $ — both monsters $ 2 $ and $ 4 $ die. In the second testcase, the initial health list is $ [2, 4, 2] $ . Three spells are casted: - the first spell on monsters $ 1 $ and $ 3 $ — both monsters have health $ 1 $ now, new health list is $ [1, 4, 1] $ ; - the second spell on monster $ 2 $ — monster $ 2 $ dies, new health list is $ [1, 0, 1] $ ; - the first spell on monsters $ 1 $ and $ 3 $ — both monsters $ 1 $ and $ 3 $ die. In the third testcase, the initial health list is $ [1, 2, 3, 4, 5] $ . Five spells are casted. The $ i $ -th of them kills the $ i $ -th monster with the second spell. Health list sequence: $ [1, 2, 3, 4, 5] $ $ \rightarrow $ $ [0, 2, 3, 4, 5] $ $ \rightarrow $ $ [0, 0, 3, 4, 5] $ $ \rightarrow $ $ [0, 0, 0, 4, 5] $ $ \rightarrow $ $ [0, 0, 0, 0, 5] $ $ \rightarrow $ $ [0, 0, 0, 0, 0] $ .Input
题意翻译
### 题目背景 Monocarp 正在玩电脑游戏。他打算杀死 $n$ 个怪兽，第 $i$ 个的血量为 $h_i$。 Monocarp 的角色有两个魔法咒语如下，都可以以任意顺序用任意次（可以不用），每次使用相当于一次操作。 1. 选择两个怪兽并**各**扣一滴血。 2. 选择一个怪兽并且直接杀死。 当一个怪兽血量为 $0$ 时，**他死了**。 求杀死所有怪兽的最少操作次数。 ### 输入 第一行一个整数 $t(1\le t\le 10^4)$ 表示数据组数。 对于每一组数据： 第一行一个整数 $n(1\le n\le 100)$ 表示怪兽数量。 第二行 $n$ 个整数 $h_1,h_2,...,h_n(1\le h_i\le 100)$ 表示每个怪兽的血量。 另外保证 $\sum n\le 2\times10^4$。 ### 输出 对于每组数据，一个数表示最少操作次数，具体见题意部分。Output
**题意翻译**
**题目背景**
Monocarp 正在玩电脑游戏。他打算杀死 $n$ 个怪兽，第 $i$ 个的血量为 $h_i$。
Monocarp 的角色有两个魔法咒语如下，都可以以任意顺序用任意次（可以不用），每次使用相当于一次操作。
1. 选择两个怪兽并**各**扣一滴血。
2. 选择一个怪兽并且直接杀死。
当一个怪兽血量为 $0$ 时，**他死了**。
求杀死所有怪兽的最少操作次数。
**输入**
第一行一个整数 $t(1\le t\le 10^4)$ 表示数据组数。
对于每一组数据：
第一行一个整数 $n(1\le n\le 100)$ 表示怪兽数量。
第二行 $n$ 个整数 $h_1,h_2,...,h_n(1\le h_i\le 100)$ 表示每个怪兽的血量。
另外保证 $\sum n\le 2\times10^4$。
**输出**
对于每组数据，一个数表示最少操作次数，具体见题意部分。
**题目描述**
Monocarp is playing a computer game. He's going to kill $ n $ monsters, the $ i $ -th of them has $ h_i $ health.
Monocarp's character has two spells, either of which he can cast an arbitrary number of times (possibly, zero) and in an arbitrary order:
- choose exactly two alive monsters and decrease their health by $ 1 $ ;
- choose a single monster and kill it.
When a monster's health becomes $ 0 $ , it dies.
What's the minimum number of spell casts Monocarp should perform in order to kill all monsters?
**输入输出格式**
**输入格式**
The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases.
The first line of each testcase contains a single integer $ n $ ( $ 1 \le n \le 100 $ ) — the number of monsters.
The second line contains $ n $ integers $ h_1, h_2, \dots, h_n $ ( $ 1 \le h_i \le 100 $ ) — the health of each monster.
The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^4 $ .
**输出格式**
For each testcase, print a single integer — the minimum number of spell casts Monocarp should perform in order to kill all monsters.
**输入输出样例**
**输入样例 #1**
```
3
4
1 2 1 2
3
2 4 2
5
1 2 3 4 5
```
**输出样例 #1**
```
3
3
5
```
**说明**
In the first testcase, the initial health list is $ [1, 2, 1, 2] $ . Three spells are casted:
- the first spell on monsters $ 1 $ and $ 2 $ — monster $ 1 $ dies, monster $ 2 $ has now health $ 1 $ , new health list is $ [0, 1, 1, 2] $ ;
- the first spell on monsters $ 3 $ and $ 4 $ — monster $ 3 $ dies, monster $ 4 $ has now health $ 1 $ , new health list is $ [0, 1, 0, 1] $ ;
- the first spell on monsters $ 2 $ and $ 4 $ — both monsters $ 2 $ and $ 4 $ die.
In the second testcase, the initial health list is $ [2, 4, 2] $ . Three spells are casted:
- the first spell on monsters $ 1 $ and $ 3 $ — both monsters have health $ 1 $ now, new health list is $ [1, 4, 1] $ ;
- the second spell on monster $ 2 $ — monster $ 2 $ dies, new health list is $ [1, 0, 1] $ ;
- the first spell on monsters $ 1 $ and $ 3 $ — both monsters $ 1 $ and $ 3 $ die.
In the third testcase, the initial health list is $ [1, 2, 3, 4, 5] $ . Five spells are casted. The $ i $ -th of them kills the $ i $ -th monster with the second spell. Health list sequence: $ [1, 2, 3, 4, 5] $ $ \rightarrow $ $ [0, 2, 3, 4, 5] $ $ \rightarrow $ $ [0, 0, 3, 4, **题意翻译** **题目背景** Monocarp 正在玩电脑游戏。他打算杀死 $n$ 个怪兽，第 $i$ 个的血量为 $h_i$。 Monocarp 的角色有两个魔法咒语如下，都可以以任意顺序用任意次（可以不用），每次使用相当于一次操作。 1. 选择两个怪兽并**各**扣一滴血。 2. 选择一个怪兽并且直接杀死。 当一个怪兽血量为 $0$ 时，**他死了**。 求杀死所有怪兽的最少操作次数。 **输入** 第一行一个整数 $t(1\le t\le 10^4)$ 表示数据组数。 对于每一组数据： 第一行一个整数 $n(1\le n\le 100)$ 表示怪兽数量。 第二行 $n$ 个整数 $h_1,h_2,...,h_n(1\le h_i\le 100)$ 表示每个怪兽的血量。 另外保证 $\sum n\le 2\times10^4$。 **输出** 对于每组数据，一个数表示最少操作次数，具体见题意部分。 **题目描述** Monocarp is playing a computer game. He's going to kill $ n $ monsters, the $ i $ -th of them has $ h_i $ health. Monocarp's character has two spells, either of which he can cast an arbitrary number of times (possibly, zero) and in an arbitrary order: - choose exactly two alive monsters and decrease their health by $ 1 $ ; - choose a single monster and kill it. When a monster's health becomes $ 0 $ , it dies. What's the minimum number of spell casts Monocarp should perform in order to kill all monsters? **输入输出格式** **输入格式** The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains a single integer $ n $ ( $ 1 \le n \le 100 $ ) — the number of monsters. The second line contains $ n $ integers $ h_1, h_2, \dots, h_n $ ( $ 1 \le h_i \le 100 $ ) — the health of each monster. The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^4 $ . **输出格式** For each testcase, print a single integer — the minimum number of spell casts Monocarp should perform in order to kill all monsters. **输入输出样例** **输入样例 #1** ``` 3 4 1 2 1 2 3 2 4 2 5 1 2 3 4 5 ``` **输出样例 #1** ``` 3 3 5 ``` **说明** In the first testcase, the initial health list is $ [1, 2, 1, 2] $ . Three spells are casted: - the first spell on monsters $ 1 $ and $ 2 $ — monster $ 1 $ dies, monster $ 2 $ has now health $ 1 $ , new health list is $ [0, 1, 1, 2] $ ; - the first spell on monsters $ 3 $ and $ 4 $ — monster $ 3 $ dies, monster $ 4 $ has now health $ 1 $ , new health list is $ [0, 1, 0, 1] $ ; - the first spell on monsters $ 2 $ and $ 4 $ — both monsters $ 2 $ and $ 4 $ die. In the second testcase, the initial health list is $ [2, 4, 2] $ . Three spells are casted: - the first spell on monsters $ 1 $ and $ 3 $ — both monsters have health $ 1 $ now, new health list is $ [1, 4, 1] $ ; - the second spell on monster $ 2 $ — monster $ 2 $ dies, new health list is $ [1, 0, 1] $ ; - the first spell on monsters $ 1 $ and $ 3 $ — both monsters $ 1 $ and $ 3 $ die. In the third testcase, the initial health list is $ [1, 2, 3, 4, 5] $ . Five spells are casted. The $ i $ -th of them kills the $ i $ -th monster with the second spell. Health list sequence: $ [1, 2, 3, 4, 5] $ $ \rightarrow $ $ [0, 2, 3, 4, 5] $ $ \rightarrow $ $ [0, 0, 3, 4,
**题目背景**
Monocarp 正在玩电脑游戏。他打算杀死 $n$ 个怪兽，第 $i$ 个的血量为 $h_i$。
Monocarp 的角色有两个魔法咒语如下，都可以以任意顺序用任意次（可以不用），每次使用相当于一次操作。
1. 选择两个怪兽并**各**扣一滴血。
2. 选择一个怪兽并且直接杀死。
当一个怪兽血量为 $0$ 时，**他死了**。
求杀死所有怪兽的最少操作次数。
**输入**
第一行一个整数 $t(1\le t\le 10^4)$ 表示数据组数。
对于每一组数据：
第一行一个整数 $n(1\le n\le 100)$ 表示怪兽数量。
第二行 $n$ 个整数 $h_1,h_2,...,h_n(1\le h_i\le 100)$ 表示每个怪兽的血量。
另外保证 $\sum n\le 2\times10^4$。
**输出**
对于每组数据，一个数表示最少操作次数，具体见题意部分。
**题目描述**
Monocarp is playing a computer game. He's going to kill $ n $ monsters, the $ i $ -th of them has $ h_i $ health.
Monocarp's character has two spells, either of which he can cast an arbitrary number of times (possibly, zero) and in an arbitrary order:
- choose exactly two alive monsters and decrease their health by $ 1 $ ;
- choose a single monster and kill it.
When a monster's health becomes $ 0 $ , it dies.
What's the minimum number of spell casts Monocarp should perform in order to kill all monsters?
**输入输出格式**
**输入格式**
The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases.
The first line of each testcase contains a single integer $ n $ ( $ 1 \le n \le 100 $ ) — the number of monsters.
The second line contains $ n $ integers $ h_1, h_2, \dots, h_n $ ( $ 1 \le h_i \le 100 $ ) — the health of each monster.
The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^4 $ .
**输出格式**
For each testcase, print a single integer — the minimum number of spell casts Monocarp should perform in order to kill all monsters.
**输入输出样例**
**输入样例 #1**
```
3
4
1 2 1 2
3
2 4 2
5
1 2 3 4 5
```
**输出样例 #1**
```
3
3
5
```
**说明**
In the first testcase, the initial health list is $ [1, 2, 1, 2] $ . Three spells are casted:
- the first spell on monsters $ 1 $ and $ 2 $ — monster $ 1 $ dies, monster $ 2 $ has now health $ 1 $ , new health list is $ [0, 1, 1, 2] $ ;
- the first spell on monsters $ 3 $ and $ 4 $ — monster $ 3 $ dies, monster $ 4 $ has now health $ 1 $ , new health list is $ [0, 1, 0, 1] $ ;
- the first spell on monsters $ 2 $ and $ 4 $ — both monsters $ 2 $ and $ 4 $ die.
In the second testcase, the initial health list is $ [2, 4, 2] $ . Three spells are casted:
- the first spell on monsters $ 1 $ and $ 3 $ — both monsters have health $ 1 $ now, new health list is $ [1, 4, 1] $ ;
- the second spell on monster $ 2 $ — monster $ 2 $ dies, new health list is $ [1, 0, 1] $ ;
- the first spell on monsters $ 1 $ and $ 3 $ — both monsters $ 1 $ and $ 3 $ die.
In the third testcase, the initial health list is $ [1, 2, 3, 4, 5] $ . Five spells are casted. The $ i $ -th of them kills the $ i $ -th monster with the second spell. Health list sequence: $ [1, 2, 3, 4, 5] $ $ \rightarrow $ $ [0, 2, 3, 4, 5] $ $ \rightarrow $ $ [0, 0, 3, 4, **题意翻译** **题目背景** Monocarp 正在玩电脑游戏。他打算杀死 $n$ 个怪兽，第 $i$ 个的血量为 $h_i$。 Monocarp 的角色有两个魔法咒语如下，都可以以任意顺序用任意次（可以不用），每次使用相当于一次操作。 1. 选择两个怪兽并**各**扣一滴血。 2. 选择一个怪兽并且直接杀死。 当一个怪兽血量为 $0$ 时，**他死了**。 求杀死所有怪兽的最少操作次数。 **输入** 第一行一个整数 $t(1\le t\le 10^4)$ 表示数据组数。 对于每一组数据： 第一行一个整数 $n(1\le n\le 100)$ 表示怪兽数量。 第二行 $n$ 个整数 $h_1,h_2,...,h_n(1\le h_i\le 100)$ 表示每个怪兽的血量。 另外保证 $\sum n\le 2\times10^4$。 **输出** 对于每组数据，一个数表示最少操作次数，具体见题意部分。 **题目描述** Monocarp is playing a computer game. He's going to kill $ n $ monsters, the $ i $ -th of them has $ h_i $ health. Monocarp's character has two spells, either of which he can cast an arbitrary number of times (possibly, zero) and in an arbitrary order: - choose exactly two alive monsters and decrease their health by $ 1 $ ; - choose a single monster and kill it. When a monster's health becomes $ 0 $ , it dies. What's the minimum number of spell casts Monocarp should perform in order to kill all monsters? **输入输出格式** **输入格式** The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains a single integer $ n $ ( $ 1 \le n \le 100 $ ) — the number of monsters. The second line contains $ n $ integers $ h_1, h_2, \dots, h_n $ ( $ 1 \le h_i \le 100 $ ) — the health of each monster. The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^4 $ . **输出格式** For each testcase, print a single integer — the minimum number of spell casts Monocarp should perform in order to kill all monsters. **输入输出样例** **输入样例 #1** ``` 3 4 1 2 1 2 3 2 4 2 5 1 2 3 4 5 ``` **输出样例 #1** ``` 3 3 5 ``` **说明** In the first testcase, the initial health list is $ [1, 2, 1, 2] $ . Three spells are casted: - the first spell on monsters $ 1 $ and $ 2 $ — monster $ 1 $ dies, monster $ 2 $ has now health $ 1 $ , new health list is $ [0, 1, 1, 2] $ ; - the first spell on monsters $ 3 $ and $ 4 $ — monster $ 3 $ dies, monster $ 4 $ has now health $ 1 $ , new health list is $ [0, 1, 0, 1] $ ; - the first spell on monsters $ 2 $ and $ 4 $ — both monsters $ 2 $ and $ 4 $ die. In the second testcase, the initial health list is $ [2, 4, 2] $ . Three spells are casted: - the first spell on monsters $ 1 $ and $ 3 $ — both monsters have health $ 1 $ now, new health list is $ [1, 4, 1] $ ; - the second spell on monster $ 2 $ — monster $ 2 $ dies, new health list is $ [1, 0, 1] $ ; - the first spell on monsters $ 1 $ and $ 3 $ — both monsters $ 1 $ and $ 3 $ die. In the third testcase, the initial health list is $ [1, 2, 3, 4, 5] $ . Five spells are casted. The $ i $ -th of them kills the $ i $ -th monster with the second spell. Health list sequence: $ [1, 2, 3, 4, 5] $ $ \rightarrow $ $ [0, 2, 3, 4, 5] $ $ \rightarrow $ $ [0, 0, 3, 4,