首页 > 试题广场 >

山峰数组计数

[编程题]山峰数组计数
  • 热度指数：169 时间限制：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
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

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

热门推荐

相关试题

山峰数组计数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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