Đếm số nghịch thế - LCOJ: Luyen Code Online

MAGB - Đếm số nghịch thế

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hieu Nguyen

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Cho một dãy gồm ~n~ số nguyên ~a_1, a_2, …, a_n~, đếm số cặp số mà số đứng sau nhỏ hơn số đứng trước. Tức là đếm số cặp ~a_i, a_j~ mà ~i < j~ và ~a_i > a_j~.

Input

Dòng đầu tiên chứa duy nhất một số nguyên dương ~n~ (số phần tử trong dãy);
Dòng thứ hai chứa ~n~ số nguyên là các phần tử ~a_1, a_2, …, a_n~

Giới hạn:

~1≤n≤10^5,1≤a_i≤10^5~

Output

In ra trên một dòng số nguyên duy nhất là số cặp nghịch thế của dãy.

Sample

Input #1

5
2 1 1 2 3

Output #1

Input #2

5
3 1 3 1 2

Output #2

Problem source: Chuyên Sơn La Online Judge

Bình luận

Hãy đọc nội quy trước khi bình luận.

ad và mọi người giúp em xem test 10 với ạ, e dùng mergeSort đúng 9/10 test (java)

import java.util.Scanner;

public class mergeSort { public static void main (String args[]){ Scanner in = new Scanner(System.in); int n = in.nextInt(); int [] a = new int[n] ; for(int i = 0; i < n; i++ ){ a[i] = in.nextInt(); } in.close(); int invest = 0; invest += mergeSort(a, 0, a.length - 1);

    System.out.println(invest);
}
public static int mergeSort(int [] a, int left, int right){
    int invest = 0;
    if(left < right){
        int middle = (right + left) / 2;
        invest +=  mergeSort(a, left, middle);
        invest += mergeSort(a, middle + 1, right);

        invest += sort(a, left, middle, right);
    }
    return invest;
}
public static int sort(int [] a, int left, int middle, int right){
    int n1 = middle - left + 1;
    int n2 = right - middle;
    int L[] = new int[n1];
    int R[] = new int[n2];

    for(int i = 0; i < n1; i++){
        L[i] = a[left + i]; 
    }
    for(int j = 0; j < n2; j++){
        R[j] = a[middle + 1 + j];
    }
    int i = 0;
    int j = 0;
    int k = left;
    int invest = 0;
    while(i < n1 && j < n2){
        if(L[i] <= R[j]){
            a[k] = L[i];
            i++;
        } else {
            a[k] = R[j];
            invest += n1 - i;
            j++;
        }
        k++;
    }

    while(i < n1){
        a[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        a[k] = R[j];
        j++;
        k++;
    }  
    return invest;
}

}