藍橋杯--排序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);
	}
}

           

記錄一下模闆