首页 > 试题广场 >

枪打出头鸟

[编程题]枪打出头鸟
  • 热度指数：5957 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
现在有n个人站成一列，第i个人的身高为。

他们人手一把玩具枪，并且他们喜欢把枪举在头顶上。
每一次练习射击，他们都会朝正前方发射一发水弹。
这个时候，第i个人射击的水弹，就会击中在他前面第一个比他高的人。
牛牛认为这样的练习十分的荒唐，完全就是对长得高的人的伤害。
于是它定义了一个荒唐度，初始为0。
对于第i个人，如中他击中了第j个人，则荒唐度加j，如果没有击中任何人，则荒唐度加0.
牛牛想问你，你能计算出荒唐度是多少吗？

示例1

输入

5,[1,2,3,4,5]

输出

0

说明

没有一个人击中任何一个人
示例2

输入

5,[5,4,3,2,1]

输出

10

说明

第二个人击中第一个人，第三个人击中第二个人，第四个人击中第三个人，第五个人击中第四个人； 1+2+3+4=10

备注:
一个整数n()
一个数组a()
a下标从0开始，
算法知识视频讲解
开通博客
头像 开车的阿Q
发表于 2021-09-04 22:11:21
描述 这是一篇面对初级coder的题解。 知识点：栈 难度：三星 题解 现在有n个人站成一列，第i个人的身高为 第i个人射击的水弹，就会击中在他前面第一个比他高的人。 对于第i个人，如果他击中了第j个人，则荒唐度加j，如果没有击中任何人，则荒唐度加0,求荒唐度 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 xqxls
发表于 2021-08-22 16:51:43
题意整理 n个人站成一列，如果某个人的前面有身高比他高的，则第一个比他高的会中枪。 只要某个人中枪了，则荒唐度会增加对应那个人的编号，求最终的荒唐度。 方法一（暴力法） 1.解题思路 直接遍历所有的人，内层循环中找到第一个比他高的人，加上对应编号，如果找到，立即终止内层循环。 2.代码实现 im 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 星云·忒弥斯
发表于 2021-08-16 20:12:26
include class Solution {public: /** * * @param n int整型 * @param k int整型 * @param card int整型vector<vector<>> * @ret 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Zero-X
发表于 2020-07-09 21:02:03
思路一： 暴力破解 对每个位置i，从后往前依次遍历[0, i-1]，即依次遍历 i-1, i-2, ..., 0，找到比a[i]大的位置，更新荒唐度值 复杂度：时间复杂度o(n^2), 思路二： 利用单调栈 设置一个单调递减的栈，将a[i]与栈顶元素进行比较，若大于栈顶元素，则不断移除栈顶元素 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 佛系的华夫饼
发表于 2023-05-01 20:37:07
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param n int整型 n个人 # @param a int整型一维数组 ai代表第i个人的高度 # @return long长整型 # class Solution: def solve( 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 球球了给孩子一个offer吧
发表于 2021-08-22 16:35:18
题目关键信息：有n个数，向左寻找第一个当前值大的第一个数，求它们所处位置的累加和方法一：单调栈定义一个类P可以存储元素的值和位置，将n个元素包装为类P入栈，如果栈非空并且当前元素值大于栈顶元素值时不断将栈中的元素出栈，直到找到第一个比当前元素值大的元素，将找到的元素索引累加得到结果 import 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-24 17:55:55
思路： 题目的主要信息： n个人的身高用数组a表示 每个人往前面开枪，会打到他前面比他高的第一个人，同时荒唐度增加被打到这个人的次序号（下标+1） 求最后总的荒唐度 方法一：暴力解法* 具体做法：*遍历数组每个人，然后每次往这个前面找到第一个大于它的元素，返回值增加下标加1.class Solut 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 胡澳治
发表于 2021-11-26 09:23:14
无他，唯long long尔 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 n个人 * @param a i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Ivy2019
发表于 2022-09-11 22:12:55
采用单调栈，从后向前遍历，栈顶元素与当前元素比较 1）当前元素 > 栈顶元素 ，说明当前元素会被打中，将当前元素位置加到结果res中；取出栈顶元素；继续取新的栈顶元素比较；将当前元素入栈 2）当前元素 < 栈顶元素 ，说明当前元素不会被打中，直接将当前元素入栈。 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客487943642号
发表于 2021-08-14 13:53:33
题目解析 每个人会击中前面第一个比自己高的人，如上图所示。用栈来存储数组的递减的子序列，从而找到每一个被击中的人。遍历数组时， 若栈顶元素大于当前数组值，则栈顶元素被击中，将数字值入栈 若栈顶元素值小于或等于数组值，则将栈顶元素弹出，判断新的栈顶值大小。若栈为空，说明没有比当前值大的，将当前数数组 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

栈
难度：
16条回答 4734浏览

热门推荐

通过挑战的用户

查看代码

相关试题

枪打出头鸟

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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