首页 > 试题广场 >

超级区间和

[编程题]超级区间和
  • 热度指数:245 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
现在有一个长度为N的数组 a, 下标范围从 0 到 N-1 , 给出 Q 组区间 l[i], r[i], 求和

注意最后的数字之和可能非常大,将最后的和除以1,000,000,007的余数输出。

输入描述:
第1行输入为N

第2行输入N个数字,代表a[0], a[1], ..., a[N-1]。

第3行输入为Q

第4行到第 3+Q 行代表Q组区间,每一行为l[i], r[i]


输出描述:
输出一个数字,代表最后所有区间的数字之和除以1,000,000,007的余数。
示例1

输入

4
1 2 3 4
2
0 2
1 3

输出

15

说明

答案为 1 + 2 + 3 + 2 + 3 + 4 = 15,因为15除以100,000,007的余数还是15,所以直接输出15即可。

备注:
数据限制:

1 <= N <= 100,000

0 <= a[i] < 10000

1 <= Q <= 100,000

1 <= l[i] <= r[i] <= N
n = int(input())
li = list(map(int, input().split()))
for i in range(1, n):
    li[i] += li[i - 1]
q = int(input())
result = 0
for i in range(q):
    i, j = list(map(int, input().split()))
    result += li[j]
    if i:
        result -= li[i - 1]
print(result % 1000000007)

发表于 2020-04-09 14:27:32 回复(3)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line1;
        while((line1 = br.readLine()) != null) {
            // 得到待求和的数组
            int n = Integer.parseInt(line1.trim());
            String line2 = br.readLine();
            String[] strArr = line2.trim().split(" ");
            int[] arr = new int[n];
            for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
            // 计算累计分布
            for(int i = 1; i < n; i++) arr[i] += arr[i - 1];
            String line3 = br.readLine();
            int Q = Integer.parseInt(line3.trim());
            String line;
            // 通过累积分布来求区间和
            String[] strIds;
            int sum = 0;
            for(int i = 0; i < Q; i++){
                line = br.readLine();
                strIds = line.trim().split(" ");
                int low = Integer.parseInt(strIds[0]);
                int high = Integer.parseInt(strIds[1]);
                sum += arr[high];
                if(low > 0) sum -= arr[low - 1];
                // 对大数进行取余
                sum %= 1000000007;
            }
            System.out.println(sum);
        }
    }
}

发表于 2020-10-13 11:16:04 回复(0)