蓝桥杯--排序1 AcWing 788. 逆序对的数量

AcWing 788. 逆序对的数量

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤100000

输入样例：

6

2 3 4 5 6 1

输出样例：

5

题意：找出有多少个 i<j 且 a[i]>a[j] 的逆序对

典型归并排序模板题

先贴个代码

public static void merge_sort(int l,int r) {
		if(l>=r) return;
		int mid=(l+r)/2;
		int i=l;
		int j=mid+1;
		merge_sort(l, mid);
		merge_sort(mid+1, r);
		int t[]=new int [r-l+2];
		int k=0;
		while(i<=mid&&j<=r) {
			if(num[i]<=num[j])
				t[k++]=num[i++];
			else {
				t[k++]=num[j++];
			}
		}
		while(i<=mid)
			t[k++]=num[i++];
		while(j<=r)
			t[k++]=num[j++];
		j=0;
		for(i=l;i<=r;i++) {
			num[i]=t[j++];
		}
	}
           

经典的一种排序算法，时间复杂度稳定在O(nlogn)

题中要求的逆序对可以在模板中微调即可，定义一个全局变量，在双指针while中记录每个逆序数对就可

代码

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;


public class Main {
	static Scanner tab = new Scanner(System.in);
	static BufferedWriter tabb = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N = 101000;
	
    static int num[]=new int [N];
	static long res=0;
    
	public static void merge_sort(int l,int r) {
		if(l>=r) return;
		int mid=(l+r)/2;
		int i=l;
		int j=mid+1;
		merge_sort(l, mid);
		merge_sort(mid+1, r);
		int t[]=new int [r-l+2];
		int k=0;
		while(i<=mid&&j<=r) {
			if(num[i]<=num[j])
				t[k++]=num[i++];
			else {
				t[k++]=num[j++];
				res+=mid-i+1;//计算数量
			}
		}
		while(i<=mid)
			t[k++]=num[i++];
		while(j<=r)
			t[k++]=num[j++];
		j=0;
		for(i=l;i<=r;i++) {
			num[i]=t[j++];
		}
	}
	
	public static void main(String[] args)   {
		int n=tab.nextInt();
		for(int i=0;i<n;i++) {
			num[i]=tab.nextInt();
		}
		merge_sort(0, n-1);
		System.out.println(res);
	}
}

           

记录一下模板