【2023米哈游-2】数组相关

米哈游拿到了一个数组a, 她用这个数组构造了一个新数组b, 其中a_i代表b数组中有a_i个i.

例如, a = [2,3,1], 则b = [1,1,2,2,2,3].解释: 2表示1有两个, 3表示2有3个, 1表示3有1个.

现给定a, 你需要求出b数组中所有b数组中连续子数组的极差之和. 由于答案过大, 对10^9+7取模.(极差指最大值减最小值)

输入描述:

第一行输入一个正整数n, 表示a数组的个数.

第二行输入n个正整数a_i, 表示a数组的元素.

示例1:

input:
2
2 1

output:
2

解题思路

一次遍历, 直接将最大和-最小和;

代码实现

import java.util.*;

public class test {
    final static long mod = (long)Math.pow(10,9)+7;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long ans = 0;
        int m;
        long sum = 0, num = 0;

        for (int i = 1; i <= n; i++) {
            m = sc.nextInt();
            if (i != 1) {
                ans += ((num*i-sum+mod)%mod)*m%mod;
                ans %= mod;
            }
            sum = (sum + (long) m *i) % mod;
            num = (num + m) % mod;
        }
        System.out.println(ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24