题解 | #计算数组的小和#

写了两版 都能AC 只不过 第一版像吃了屎一样难看

这题关键是

只要在左边数组 找到一个小的 则右数组都会小直接乘于右边数组剩下的个数即可

第一版

想法是 只要找到右边大的时候 此时在 左边数组之前 arr[l] 的都是小的 遍历把它们都加上 想法没有第二版精妙

import java.io.*;

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s = reader.readLine().split(" ");
int m = Integer.valueOf(s[0]);
int[] arr = new int[m];
s = reader.readLine().split(" ");
for (int i = 0; i < m; i++) {
arr[i] = Integer.valueOf(s[i]);
}
System.out.println(mergerSort(arr, 0, m-1 ));
System.out.println();


}
static int mergerSort(int[] arr, int L, int R) {
    if (L >= R)
        return 0;
    int mid = L + ((R - L) >> 1);
    int l = L;
    int r = mid+1;
    int i = 0;
    int count = 0;
    count += (mergerSort(arr, L, mid) + mergerSort(arr, r , R));
    int[] nArr = new int[R - L + 1];
    while (l <= mid || r <= R) {
        // l==mid 会取到
        if (l > mid) {
            nArr[i] = arr[r++];
            for (int j = L; j < l; j++)
                count +=  arr[j];
        } else if (r > R) {
            nArr[i] = arr[l++];
        } else if (arr[l] <= arr[r]) {
            nArr[i] = arr[l++];
        } else {
            nArr[i] = arr[r++];
            for (int j = L; j < l; j++)
                count +=  arr[j];
        }
        i++;
    }
    for (int j = 0; j < i; j++)
        arr[L + j] = nArr[j];
    return count;
    }
}

第二版：

import java.io.*;

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s = reader.readLine().split(" ");
int m = Integer.valueOf(s[0]);
int[] arr = new int[m];
s = reader.readLine().split(" ");
for (int i = 0; i < m; i++) {
arr[i] = Integer.valueOf(s[i]);
}
System.out.println(mergerSort(arr, 0, m-1 ));
System.out.println();


}
static long mergerSort(int[] arr, int L, int R) {
    if (L >= R)
        return 0;
    int mid = L + ((R - L) >> 1);
    int l = L;
    int r = mid+1;
    int i = 0;
    long count = 0;
    count += (mergerSort(arr, L, mid) + mergerSort(arr, r , R));
    int[] nArr = new int[R - L + 1];
    while (l <= mid || r <= R) {
        // l==mid 会取到
        if (l > mid) {
            nArr[i] = arr[r++];
        } else if (r > R) {
            nArr[i] = arr[l++];
        } else if (arr[l] <= arr[r]) {
            //绝了 这里 我之前考虑的和这个不一样 而是相反
            count += (R-r+1) * arr[l];
            nArr[i] = arr[l++];
        } else {
            nArr[i] = arr[r++];
        }
        i++;
    }
    for (int j = 0; j < i; j++)
        arr[L + j] = nArr[j];
    return count;
}

}