Problem 4132 --A任务执行

4132: A任务执行

上一题 正确率: $320.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $5$ 正确数量 $16$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

有n个不同的任务需要完成，完成任务需要耗费一定的时间。一旦开始进行某个任务，既不能中途暂停 或终止这个任务，也不能同时进行另一个任务。此外，每当一个耗时不为0的任务被完成，剩余的其他 任务所需要的时间都减少1（最低减至0，先前已经完成的任务不受影响）。 给出所有任务的耗时，请求出完成它们所需的最短时间。

Input

输入的第1行包含1个整数n，表示任务数。 接下来1行，包含n个整数，第i个整数表示完成第i个任务所需要的时间。

Output

求出完成它们所需的最短时间。

Sample Input复制

6
1 1 4 5 1 4

Sample Output复制

8

提示


• 1 ≤ n ≤ 10^5 

• 1 ≤ ai ≤ 10^9 

• 有30%的数据，n ≤ 10


一种可能的方案是：
1. 完成一个耗时为1的任务，剩下的任务分别耗时0, 3, 4, 0, 3；
2. 完成两个耗时为0的任务，剩下3, 4, 3；
3. 完成一个耗时为4的任务，剩下2, 2；
4. 完成一个耗时为2的任务，剩下1；
5. 完成一个耗时为1的任务。
这个方案的总耗时是1 + 0 + 0 + 4 + 2 + 1 = 8。不存在总耗时小于8的方案。


推荐代码 查看4132 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$2 $ms] jyl 1194782 2025-05-11 14:34:05
内存最少[$1192 $KB] 储俊杰 1101596 2024-05-06 11:19:52
第一AC 储俊杰 1101593 2024-05-06 11:14:58
第一挑战 储俊杰 1101593 2024-05-06 11:14:58

赛题来源/所属竞赛 安徽省机器人大赛程序设计赛道网络赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
AOJ