蓝桥杯准备（前缀和差分）

import java.util.Scanner;
public class qianzhuihe {public static void main(String[] args) {int N,M;Scanner sc=new Scanner(System.in);N=sc.nextInt();M=sc.nextInt();int []trees=new int[N+1];//设为N+1的意义，防止越界int []prefixSum=new int[N+1];for(int i=1;i<=N;i++){trees[i]=sc.nextInt();prefixSum[i]=prefixSum[i-1]+trees[i];//}for(int i=0;i<M;i++){int l=sc.nextInt();int r=sc.nextInt();int cost=prefixSum[r]-prefixSum[l-1];System.out.println(cost);}sc.close();
}}

注意点：为了防止访问越界，使trees[i]从trees[1]开始，使当l=1时不会越界

前缀和优点：增加了空间复杂度，但查询的时间复杂度为O（1），适用于查询次数过多的情况

import java.util.Scanner;public class practise1 {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int []nums=new int[n+1];int []pre=new int[n+1];//自动赋值为0for(int i=1;i<=n;i++){nums[i]=sc.nextInt();pre[i]=pre[i-1]+nums[i];}int sum=0;for(int i=1;i<=n;i++){sum+=nums[i]*(pre[n]-pre[i]);}System.out.println(sum);}
}

注意为了防止溢出：应该使用long类型

贪心算法：掉头最多只能有一次

import java.util.Scanner;
public class i {public  static void main(String[]args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();//记录最长步数int []left=new int[n];int []right=new int[n];//记录左右矿洞int cnt=0;//记录0出现的次数for(int i=0;i<n;i++){int x=sc.nextInt();if(x<0){left[-x]++;//相当于哈希表，记录该数出现的次数,在输入的数不重复的情况下，最多为1}else if(x>0){right[x]++;}else if(x==0){cnt++;}}for(int i=1;i<=m;i++){//将两个原记录矿石数的数组直接在原基础5上改变成前缀和数组,不用再创建数组浪费空间复杂度left[i]+=left[i-1];right[i]+=right[i-1];//left[i]表达从0-i索引的矿洞的总数量，有一个类似于递归的数组，left[i-1]表达是从0-(i-1)的矿洞的总数量，再加上当前i位置的矿洞的数量}int ans=0;//记录在总步长限制的情况下，最长能经过的矿数for(int i=1;i<=m/2;i++)//一一枚举，表示从0开始，可以向前走1步，到m/2步，贪心算法，最多不回头或者一次回头{int t=right[i];//表示先向右走i步途径的矿洞数if(m-2*i>0){t+=left[m-2*i];}//加上折返路上途径的矿的数量ans=Math.max(t,ans);t=left[i];//表示先向左走if(m-2*i>0){t+=right[m-2*i];}ans=Math.max(t,ans);//再次更新最大值，比较先向右走还是先向左走值更大}System.out.println(ans+cnt);sc.close();}
}

如果前缀和计算到 n

• n 表示 矿洞的个数，但 矿洞的坐标范围不一定是 n。

• 假设 n = 5，矿洞位置可能是 { -10, -5, 3, 8, 15 }，那么 left[i] 需要处理 负数索引，但数组索引不能是负的。

• 但如果 最大步数 m 只有 6，我们 永远不可能到达 x = -10 或 x = 15，所以 存储它们是浪费的。

• 计算到 n 可能会导致 数组越界或者不必要的存储。

• 如果前缀和计算到 m

• m 是 最多能走的步数，所以矿洞的前缀和只需要计算到 最多走 m 的范围。

• 假设 m = 6，那么：

  • 左侧矿洞 只有 x ∈ [-6, -5, -4, -3, -2, -1] 才有意义。

  • 右侧矿洞 只有 x ∈ [1, 2, 3, 4, 5, 6] 才有意义。

• 这样，只计算我们能到达的位置的前缀和，节省空间。