首页 > 试题广场 >

小红的小踏前斩

[编程题]小红的小踏前斩
  • 热度指数：1382 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有n个怪物排成一排，每只怪物的血量为a_i。
小红有一个技能：小踏前斩。效果是：选择一只怪物，对这只怪物造成1点伤害，并发出剑气，对下一个怪物造成2点伤害。（注：若下一个怪物已死亡，则剑气会打在尸体上，并不会向后穿透）。
小红可以对尸体发出踏前斩，剑气同样可以溅射到后面的怪物。但小红无法对第一个怪物前面的空气发出踏前斩用来溅射第一个怪物。
小红想至少击杀2只怪物，她想知道自己需要最少发出多少次小踏前斩？

输入描述:
第一行输入一个正整数n，代表怪物的数量。
第二行输入n个正整数a_i，代表每只怪物的血量。
2\leq n\leq 200000
1\leq a_i \leq 10^9


输出描述:
一个正整数，代表踏前斩的最小次数。
示例1

输入

2
2 6

输出

3

说明

对第一个怪物释放两次踏前斩，然后对它的尸体再放一次踏前斩。
示例2

输入

4
2 3 2 5

输出

2

说明

对第一个怪物放一次踏前斩，再对第二个怪物放一次踏前斩即可。此时第二只怪物、第三只怪物死亡。
算法知识视频讲解
开通博客
头像 Mag1c0nch
发表于 2024-11-29 00:05:40
很讨厌的分类讨论，就是分别讨论杀死的两个怪是相邻还是不相邻，是第一个还是不是第一个 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 missay情玖
发表于 2024-12-01 20:41:34
#include <algorithm> #include <climits> #include <iostream> #include <vector> #include <cmath> using namespace std; int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 wdnmdwdnmd
发表于 2024-12-04 17:55:51
#include <cstdio> #include <iostream> #include <vector> #include "bits/stdc++.h" using namespace std; const int maxn = 2e5 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

来自：22年秋招蚂蚁编程题精选
难度：
7条回答 4522浏览

热门推荐

通过挑战的用户

查看代码

相关试题

小红的小踏前斩

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号