首页 > 试题广场 >

山峰数组计数

[编程题]山峰数组计数

热度指数：623 时间限制：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)$ 。

输入描述:

第一行输入一个整数 ，表示数组  的长度。

第二行输入  个整数 ，表示数组元素。

输出描述:

输出一个整数，表示可行二元组的数量。

示例1

输入

5
1 2 3 4 5

输出

算法知识视频讲解

想吃开封菜的柯基在写文章

macro_rules! read_line {
    ($buf:ident) => {
        $buf.clear();
        std::io::stdin().read_line(&mut $buf)?;
    };
}

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let mut buf = String::new();
    read_line!(buf);
    read_line!(buf);
    let nums = buf
        .trim()
        .split(' ')
        .map(|s| s.parse::<usize>().unwrap())
        .collect::<Vec<_>>();
    let n = nums.len();
    let mut sum = vec![0; n + 1];
    for i in 0..n {
        sum[i + 1] = sum[i] + nums[i];
    }
    // [0, i) [i, j) [j, n) 2 * sum[j]  > sum[n] + sum[i]
    // sum[j] - sum[i] > sum[i];
    // sum[j] > 2 * sum[i]
    let mut ret = 0;
    for i in 1..n - 1 {
        let target = (sum[i] * 4).max(sum[n] + sum[i]);
        let mut left = i + 1;
        let mut right = n;
        while left < right {
            let mid = (left + right) >> 1;
            if sum[mid] * 2 > target {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        ret += n - right;
    }
    print!("{}", ret);
    Ok(())
}

发表于 2026-01-24 13:23:09 回复(0)