归并排序巧解计算数组的小和问题

在这里插入图片描述这道题如果用暴力的解法，对每一个元素遍历它左边的所有元素，累加比它更小的数，代码逻辑当然非常简单，但是时间复杂度会达到$O(n^2)$，如果数组的长度n达到1e5时，我们估算一下啊，1e10次的运算很明显会超时，这么做会通不过测试系统。

而借助归并排序的思想，是可以将这道题的时间复杂度优化到$O(nlogn)$的。

下面介绍代码逻辑：

1.首先定义全局变量用于存储数据与临时数组

1
2
3
4


public static int MAXN = 100001;  // 数组最大长度
public static int[] arr = new int[MAXN];  // 存储原始数组
public static int[] help = new int[MAXN];  // 合并时的临时数组
public static int n;  // 数组实际长度

2.输入输出的处理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


public static void main(String[] args)throws IOException{
    // 读入
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    // 输出
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    // 处理多组输入（直到文件结束）
    while(in.nextToken()!=StreamTokenizer.TT_EOF){
        n = (int) in.nval;  // 读取数组长度
        // 读取数组元素
        for(int i=0;i<n;i++){
            in.nextToken();
            arr[i]=(int)in.nval;
        }
        // 计算小和并输出
        out.println(smallSum(0,n-1));
    }
    out.flush();  // 刷新缓冲区，确保输出
    out.close();  // 关闭输出流
}

3.分治函数

1
2
3
4
5
6
7
8


public static long smallSum(int l,int r){
    if(l==r){  // base case
        return 0;
    }
    int m = l+((r-l)>>1);  // 中间位置，将数组分成 [l,m] 和 [m+1,r]
    // 分治逻辑：左半部分小和 + 右半部分小和 + 合并时的小和
    return smallSum(l,m) + smallSum(m+1,r) + merge(l,m,r);
}

4.合并函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


public static long merge(int l,int m,int r){
    long ans = 0;  // 存储当前合并阶段的小和
    // 统计小和
    for(int j=m+1, i=l, sum=0; j<=r; j++){  
        // 累积左数组 L 中比当前 R[j] 小的元素和
        while(i<=m && arr[i] <= arr[j]){
            sum += arr[i++];
        }
       
        ans += sum;
    }

    // 合并两个有序子数组到 help 数组
    int i = l;        
    int a = l;        
    int b = m+1;      
    while(a <= m && b <= r){  // 两个数组都没遍历完
        // 取较小的元素放入 help
        help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
    }
    // 处理左数组剩余元素
    while(a <= m){
        help[i++] = arr[a++];
    }
    // 处理右数组剩余元素
    while(b <= r){
        help[i++] = arr[b++];
    }

    // 将 help 中的有序数组拷贝回 arr
    for(i=l; i<=r; i++){
        arr[i] = help[i];
    }

    return ans;  
}

代码链接 链接：小和提取码：2JMV