题解 | 山峰数组计数

import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) throws IOException {

        // 使用BufferedReader读取输入，使用PrintWriter输出结果
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 读取整数n，表示数组的长度
        int n = Integer.parseInt(br.readLine().trim());
        // 创建长度为n的数组P，用于存储输入的数值
        long[] P = new long[n];
        // 创建长度为n+1的前缀和数组preSum，preSum[0]=0
        long[] preSum = new long[n+1];

        // 读取一行输入，按空格分割成字符串数组
        String[] s= br.readLine().trim().split("\\s+");
        // 计算前缀和
        for(int i=0;i<n;i++){
            // 将字符串转换为长整型并存入数组P
            P[i]= Long.parseLong(s[i]);
            // 计算前缀和，preSum[i+1]表示前i个元素的和
            preSum[i+1]=preSum[i]+P[i];
        }

        // 初始化总和变量total
        long total = 0;

        // 遍历数组，从第2个元素开始到倒数第2个元素
        for (int j=2;j<n;j++){
            // 计算limit1，即(preSum[j]-1)/2
            long limit1 = (preSum[j]-1)/2;
            // 计算limit2，即2*preSum[j]-preSum[n]-1
            long limit2 = 2*preSum[j]-preSum[n]-1;
            // 取limit1和limit2中的较小值作为阈值
            long threshold = Math.min(limit1,limit2);

            // 如果阈值大于等于第一个元素的前缀和
            if (threshold >= preSum[1]){
                // 调用upper函数计算符合条件的元素个数
                int count = upper(preSum,1,j-1,threshold);
                // 将count累加到total中
                total += count;
            }
        }



        // 输出最终结果
        out.println(total);

        // 刷新输出流，确保所有输出都被写入
        out.flush();
        // 关闭输出流，释放资源
        out.close();
        // 关闭输入流，释放资源
        br.close();
    }

/**
 * 在有序数组中查找最后一个小于等于目标值的元素的位置，并返回满足条件的元素个数
 * @param preSum 有序数组，表示前缀和数组
 * @param left 查找范围的左边界
 * @param right 查找范围的右边界
 * @param target 目标值
 * @return 返回在[left, right]范围内小于等于target的元素个数
 */
    private static int upper(long[] preSum,int left,int right,long target){
        int low = left,high = right;    // 初始化查找范围的左右边界
        int ans = 0;                    // 初始化答案变量

        // 执行二分查找
        while(low<=high){
            int mid = low +((high-low)>>1);   // 计算中间值，使用位运算优化替代除法

                                        // 这种写法可以避免(low+high)可能导致的整数溢出问题
            // 检查中间值是否满足条件
            if(preSum[mid]<=target){    // 如果中间值小于等于目标值
                ans = mid;              // 更新答案为当前位置
                low = mid+1;            // 在右半部分继续查找
            }else{                      // 如果中间值大于目标值
                high = mid-1;           // 在左半部分继续查找
            }
        }
    // 返回结果：如果找到满足条件的元素，返回其个数；否则返回0
        return ans>0?(ans-left+1):0;
    }
}