前缀和_牛客博客

&&可以通俗的理解为数列前n项的和，或者可以理解为数组中前n项目之和。

<1>一维数组的前缀和，代码实现：

 import java .util.Scanner;
 public class Main{
public static void main(String[]args)
{
    Scanner input =new Scanner(System.in);
    int n= input.nextInt();
    int []ant=new int[1000];
    int []arr=new int[1000];
    for(int i=0;i<n;i++)
    {
        ant[i]= input.nextInt();
    }
    arr[0]=ant[0];
    for(int i=1;i<n;n++)
    {
        arr[i]=arr[i-1]+ant[i];
    }
    for(int i=0;i<n;i++)
    {
        System.out.print(arr[i]+" ");
    }

}
}

例题& 来源：牛客网

小沙非常好客，小沙有一家超市，超市里面有为 n 件商品，小沙有 Q 个问题，小沙想问问你，如果小沙想要让你挑选最多 k 个价值不大于 x 的商品，请问你能挑选的价值和最大为多少。

输入描述：

第一行输入两个整数1<=n<=10的5次方，1<=q<=10的5次方，代表商品个数以及询问次数

第二行输入n个数字代表商品价格序列a

随后q行

每行两个正整数k,x;

输出描述：

每次询问输出一行代表答案

例如

5 3

1 3 3 5 10

4 3

2 3

3 10

输出

<解题思路分析>

前缀和+二分

import java.util.*;

public class Main {
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    
    int n = scanner.nextInt();
    long q = scanner.nextLong();
    long[] a = new long[n + 1];
    long[] b = new long[n + 1];
    for (int i = 1; i <= n; i++) {
        a[i] = scanner.nextLong();
    }
    Arrays.sort(a);
    for (int i = 1; i <= n ; i++) {
        b[i] = b[i - 1] + a[i];
    }
    for (long i = 0; i < q; i++) {
        long k = scanner.nextLong();
        long x = scanner.nextLong();
        long sum = 0;
        long temp=upperBound(a,x,n);
        if(temp>k) sum=b[(int)temp]-b[(int)(temp-k)];
        else sum=b[(int)temp];
       System.out.println(sum);
    }
    
}
public static long upperBound(long[] a,long x,long n){//二分法
    long l=1;long r=n;
    while (l<=r){
        long mid=(r+l)/2;
        if(a[(int)mid]<=x) l=mid+1;
        else r=mid-1;
    }
    return r;
}
}