首页 > 试题广场 >

山峰数组计数

[编程题]山峰数组计数
  • 热度指数：353 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}定义一个山峰数组为长度为 3 的数组 [a_1,a_2,a_3]，满足 a_1<a_2 且 a_2>a_3。

\hspace{15pt}给定一个长度为 n 的正整数数组 P，你需要选择两个下标 i,j\ (1\leqq i<j<n)，并将 P 划分成三个非空连续子数组：
\hspace{23pt}\bullet\, b_1 = \displaystyle\sum_{k=1}^{i} P_k；
\hspace{23pt}\bullet\, b_2 = \displaystyle\sum_{k=i+1}^{j} P_k；
\hspace{23pt}\bullet\, b_3 = \displaystyle\sum_{k=j+1}^{n} P_k。

\hspace{15pt}若三元组 [b_1,b_2,b_3] 构成一个山峰数组，则称二元组 (i,j) 可行。请计算共有多少个不同的可行二元组 (i,j)。

输入描述:
\hspace{15pt}第一行输入一个整数 n\ \left(3\leqq n\leqq 2\times10^5\right)，表示数组 P 的长度。

\hspace{15pt}第二行输入 n 个整数 P_1,P_2,\dots,P_n\ \left(1\leqq P_i\leqq10^6\right)，表示数组元素。


输出描述:
\hspace{15pt}输出一个整数，表示可行二元组的数量。
示例1

输入

5
1 2 3 4 5

输出

2
算法知识视频讲解
开通博客
头像 斩瑾
发表于 2024-06-16 19:08:22
一道前缀和的应用 最快得到一个区间的和就用前缀和，其中暴力两次循环可以得到符合题目性质的解的数量，但肯定会超时，这时就需要考虑能不能优化成n的规模解决问题，根据前缀和单调递增的性质可以发现随着遍历i的取值j一定只会往后增大这时只要当每一次循环时找到符合要求的j的位置，如果符合当前i的位置的性质要求答 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 Silencer76
发表于 2025-08-13 16:51:03
题目链接 山峰数组计数 题目描述 定义一个山峰数组为一个长度为 3 的数组 ，满足 且 。 给定一个长度为 的正整数数组 。你需要选择两个下标 和 （），并将数组 划分成三个非空的连续子数组，其元素和分别为： 若三元组 构成一个山峰数组，则称二元组 是一个可行的二元组。请计算共 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-01 11:20:44
题目链接 山峰数组计数 题目描述 给定一个长度为 的正整数数组 。你需要选择两个下标 （），并将 划分成三个非空连续子数组：，，。 若这三个子数组的和满足 且 ，则称二元组 可行。请计算共有多少个不同的可行二元组。 解题思路 这是一个计数问题。一个朴素的想法是遍历所有可能的 对，然后计算三 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客242693846号
发表于 2025-07-31 16:30:10
import bisect n = int(input()) nums = list(map(int, input().split())) # 构建前缀和 sum_nums = [0] for num in nums: sum_nums.append(sum_nums[-1] + num 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

来自：华为机试编程模拟题2
难度：
1条回答 216浏览

热门推荐

相关试题

山峰数组计数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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