A16346 | Smilo and Monsters
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
A boy called Smilo is playing a new game! In the game, there are $n$ hordes of monsters, and the $i$ -th horde contains $a_i$ monsters. The goal of the game is to destroy all the monsters. To do this, you have two types of attacks and a combo counter $x$ , initially set to $0$ :
- The first type: you choose a number $i$ from $1$ to $n$ , such that there is at least one monster left in the horde with the number $i$ . Then, you kill one monster from horde number $i$ , and the combo counter $x$ increases by $1$ .
- The second type: you choose a number $i$ from $1$ to $n$ , such that there are at least $x$ monsters left in the horde with number $i$ . Then, you use an ultimate attack and kill $x$ monsters from the horde with number $i$ . After that, $x$ is reset to zero.
Your task is to destroy all of the monsters, meaning that there should be no monsters left in any of the hordes. Smilo wants to win as quickly as possible, so he wants to the minimum number of attacks required to win the game.
- The first type: you choose a number $i$ from $1$ to $n$ , such that there is at least one monster left in the horde with the number $i$ . Then, you kill one monster from horde number $i$ , and the combo counter $x$ increases by $1$ .
- The second type: you choose a number $i$ from $1$ to $n$ , such that there are at least $x$ monsters left in the horde with number $i$ . Then, you use an ultimate attack and kill $x$ monsters from the horde with number $i$ . After that, $x$ is reset to zero.
Your task is to destroy all of the monsters, meaning that there should be no monsters left in any of the hordes. Smilo wants to win as quickly as possible, so he wants to the minimum number of attacks required to win the game.
输入格式
The first line contains a single integer $t$ ( $1 \leq t \leq 10^4$ ) — the number of test cases. The descriptions of the test cases follow.
The first line of each input data set contains a single integer $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ) — the number of hordes of monsters.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ ) — the number of monsters in each horde.
It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot {10^5}$ .
The first line of each input data set contains a single integer $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ) — the number of hordes of monsters.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ ) — the number of monsters in each horde.
It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot {10^5}$ .
输出格式
For each test case, out put the minimum number of attacks required to kill all monsters.
输入输出样例
输入 #1
4 4 1 3 1 1 4 1 2 1 1 6 3 2 1 5 2 4 2 1 6
输出 #1
4 4 11 5
In the first test case, we can use an attack of the first type on the $1$ -st, $3$ -rd and $4$ -th hordes, and then use an attack of the second type to finish off the $2$ -nd horde. We need $4$ attacks in total.
In the second test case, we can use an attack of the first type on the $1$ -st and $3$ -rd hordes, then use an attack of the second type to finish off the $2$ -nd horde, and then use an attack of the first type on the $4$ -th horde. We need $4$ attacks in total.
In the fourth test case, we can use an attack of the first type once on the $1$ -st horde, twice on the $2$ -nd horde, and then use an attack of the second type on the $2$ -nd horde, and finally use an attack of the first type to finish off the $2$ -nd horde. We need $5$ attacks in total.
In the second test case, we can use an attack of the first type on the $1$ -st and $3$ -rd hordes, then use an attack of the second type to finish off the $2$ -nd horde, and then use an attack of the first type on the $4$ -th horde. We need $4$ attacks in total.
In the fourth test case, we can use an attack of the first type once on the $1$ -st horde, twice on the $2$ -nd horde, and then use an attack of the second type on the $2$ -nd horde, and finally use an attack of the first type to finish off the $2$ -nd horde. We need $5$ attacks in total.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted