![]()
思路
![]()
求解代码
publicstaticvoidmain(String[]args)throwsIOException{// 使用BufferedReader读取输入，使用PrintWriter输出结果BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));// 读取整数n，表示数组的长度intn=Integer.parseInt(br.readLine().trim());// 创建长度为n的数组P，用于存储输入的数值long[]P=newlong[n];// 创建长度为n+1的前缀和数组preSum，preSum[0]=0long[]preSum=newlong[n+1];// 读取一行输入，按空格分割成字符串数组String[]s=br.readLine().trim().split("\\s+");// 计算前缀和for(inti=0;i<n;i++){// 将字符串转换为长整型并存入数组PP[i]=Long.parseLong(s[i]);// 计算前缀和，preSum[i+1]表示前i个元素的和preSum[i+1]=preSum[i]+P[i];}// 初始化总和变量totallongtotal=0;// 遍历数组，从第2个元素开始到倒数第2个元素for(intj=2;j<n;j++){// 计算limit1，即(preSum[j]-1)/2longlimit1=(preSum[j]-1)/2;// 计算limit2，即2*preSum[j]-preSum[n]-1longlimit2=2*preSum[j]-preSum[n]-1;// 取limit1和limit2中的较小值作为阈值longthreshold=Math.min(limit1,limit2);// 如果阈值大于等于第一个元素的前缀和if(threshold>=preSum[1]){// 调用upper函数计算符合条件的元素个数intcount=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的元素个数 */privatestaticintupper(long[]preSum,intleft,intright,longtarget){intlow=left,high=right;// 初始化查找范围的左右边界intans=0;// 初始化答案变量// 执行二分查找while(low<=high){intmid=low+((high-low)>>1);// 计算中间值，使用位运算优化替代除法// 这种写法可以避免(low+high)可能导致的整数溢出问题// 检查中间值是否满足条件if(preSum[mid]<=target){// 如果中间值小于等于目标值ans=mid;// 更新答案为当前位置low=mid+1;// 在右半部分继续查找}else{// 如果中间值大于目标值high=mid-1;// 在左半部分继续查找}}// 返回结果：如果找到满足条件的元素，返回其个数；否则返回0returnans>0?(ans-left+1):0;}
