逆序对

[编程题]逆序对

热度指数：5804 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

作为程序员的小Q，他的数列和其他人的不太一样，他有 $2^n$ 个数。

老板问了小Q一共 m次，每次给出一个整数 $q_i (1 <= i <= m)$ , 要求小Q把这些数每 $2^{q_i}$ 分为一组，然后把每组进行翻转，小Q想知道每次操作后整个序列中的逆序对个数是多少呢？

例如:

对于序列1 3 4 2，逆序对有(4, 2),(3, 2),总数量为2。

翻转之后为2 4 3 1，逆序对有(2, 1),(4, 3), (4, 1), (3, 1),总数量为4。

输入描述:

第一行一个数
第二行个数，表示初始的序列()
第三行一个数
第四行m个数表示

输出描述:

m行每行一个数表示答案。

示例1

输入

输出

说明

初始序列2 1 4 3
 ->
第一次：1 2 3 4 -> 逆序对数为0
 ->
第二次：4 3 2 1 -> 逆序对数为6
 ->
第三次：4 3 2 1 -> 逆序对数为6
 ->
第四次：1 2 3 4 -> 逆序对数为0

算法知识视频讲解

Java

泽泽补眠中

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int N = 1 << n;
        //正序数组
        int[] a = new int[N];
        //逆序数组
        int[] b = new int[N];
        long[] order = new long[n + 1];
        long[] reOrder = new long[n + 1];
        for (int i = 0; i < N; ++i) {
            //正序添加元素
            a[i] = sc.nextInt();
            //倒序添加元素
            b[N - 1 - i] = a[i];
        }
        int[] tmp = new int[N];
        //一次归并求逆序对数
        mergeCount(a, 0, N - 1, tmp, reOrder, n);
        //一次归并求顺序对数
        mergeCount(b, 0, N - 1, tmp, order, n);

        int m = sc.nextInt();
        while (m-- > 0) {
            // 2^i 个元素为一组进行翻转
            int q = sc.nextInt();
            for (int i = 1; i <= q; ++i) {
                long temp = order[i];
                order[i] = reOrder[i];
                reOrder[i] = temp;
            }
            long count = 0;
            for (int i = 1; i <= n; ++i) {
                count += reOrder[i];
            }
            System.out.println(count);
        }
    }
    private static void mergeCount(int[] nums, int left, int right, int[] temp, long[] reOrder, int index) {
        if (left >= right) return;
        int mid = (left + right) >>> 1;
        mergeCount(nums, left, mid, temp, reOrder, index - 1);
        mergeCount(nums, mid + 1, right, temp, reOrder, index - 1);
        int i = left, j = mid + 1;

        while (i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                reOrder[index] += (mid + 1 - i);
                ++j;
            } else {
                ++i;
            }
        }
        merge(nums, left, mid, right, temp);
    }

    private static void merge(int[] nums, int left, int mid, int right, int[] temp) {
        System.arraycopy(nums, left, temp, left, right - left + 1);
        int i = left, j = mid + 1, k = left;

        while (i <= mid && j <= right) nums[k++] = temp[i] <= temp[j] ? temp[i++] : temp[j++];
        while (i <= mid) nums[k++] = temp[i++];
        while (j <= right) nums[k++] = temp[j++];
    }
}

发表于 2020-09-22 17:43:16 回复(0)

Java

挂在这里不倒在这里

Java只通过60%用例，咋办啊？应该改哪里啊？

import java.util.*;
public class Main{
    public static long count = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] data = new int[(int)Math.pow(2,n)];
        for(int i=0; i<(int)Math.pow(2,n); i++){
            data[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] q = new int[m];
        for(int i=0; i<m; i++){
            q[i] = sc.nextInt();
            data = reverse(q[i], data);
        }
    }
    public static int[] reverse(int q, int[] data){
        int m,n,k;
        int[] re = new int[data.length];
        int[] re2 = new int[data.length];
        k = (int)(Math.pow(2,q));
        for(int i=0; i<data.length; i++){
            m = i/k;
            n = i%k;
            re[i] = data[(m+1)*k-n-1];
            re2[i] = data[(m+1)*k-n-1];
        }
        getReverseCount(re2);
        System.out.println(count);
        count = 0;
        return re;
    }
 
    //使用归并排序方法计算数组A中的逆序对数
    public static void getReverseCount(int[] A) {
        if(A.length > 1) {
            int[] leftA = getHalfArray(A, 0);   //数组A的左半边元素
            int[] rightA = getHalfArray(A, 1);  //数组A的右半边元素
            getReverseCount(leftA);
            getReverseCount(rightA);
            mergeArray(A, leftA, rightA);
        }
    }
    //根据judge值判断，获取数组A的左半边元素或者右半边元素
    public static int[] getHalfArray(int[] A, int judge) {
        int[] result;
        if(judge == 0) {   //返回数组A的左半边
            result = new int[A.length / 2];
            for(int i = 0;i < A.length / 2;i++)
                result[i] = A[i];
        } else {    //返回数组的右半边
            result= new int[A.length - A.length / 2];
            for(int i = 0;i < A.length - A.length / 2;i++)
                result[i] = A[A.length / 2 + i];
        }
        return result;
    }
    //合并数组A的左半边和右半边元素，并按照非降序序列排列
    public static void mergeArray(int[] A, int[] leftA, int[] rightA){
        int len = 0;
        int i = 0;
        int j = 0;
        int lenL = leftA.length;
        int lenR = rightA.length;
        while(i < lenL && j < lenR) {
            if(leftA[i] > rightA[j]) {
                A[len++] = rightA[j++];
                count += (lenL - i);
            } else {
                A[len++] = leftA[i++];
            }
        }
        while(i < lenL)
            A[len++] = leftA[i++];
        while(j < lenR)
            A[len++] = rightA[j++];
    }
}

发表于 2020-02-18 20:20:32 回复(2)