首页 > 试题广场 >

山峰数组计数

[编程题]山峰数组计数
  • 热度指数：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
算法知识视频讲解
添加回答
牛客469391155号头像 牛客469391155号
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<long long> ps(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        int p;
        cin >> p;
        ps[i + 1] = ps[i] + p;
    }
    long long count = 0;
    for (int i = 1; i <= n - 2; ++i) {
        auto it1 = upper_bound(ps.begin() + i + 1, ps.begin() + n, 2 * ps[i]);
        long long threshold = ps[n] + ps[i];
        int left = i + 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (2 * ps[mid] > threshold) {
                right = mid;
            } else {
            }
        }
        auto it2 = ps.begin() + left;
        auto start_it = max(it1, it2);
        count += distance(start_it, ps.begin() + n);
    }
    cout << count << endl;
    return 0;
}
发表于 2025-10-14 20:24:27 回复(0)
提交观点

问题信息

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

热门推荐

相关试题

山峰数组计数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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