求逆序對數

總時間限制: 

500ms

記憶體限制: 

65536kB

描述

對于一個長度為N的整數序列A，滿足i < j 且 Ai > Aj.的數對(i,j)稱為整數序列A的一個逆序

請求出整數序列A的所有逆序對個數

輸入

輸入包含多組測試資料，每組測試資料有兩行

第一行為整數N(1 <= N <= 20000)，當輸入0時結束

第二行為N個整數，表示長為N的整數序列

輸出

每組資料對應一行，輸出逆序對的個數

樣例輸入

5
1 2 3 4 5
5
5 4 3 2 1
1
1
0      

樣例輸出

0
10
0      

錯誤思路:

  首先跟大家講一下，我最開始的時候的思路，首先輸入n和a[1~n]，如果n=0就直接break退出了（直接return也是可以的），然後進行雙重for循環j=i+1保證i<j的，然後進行判斷，如果a[i]>a[j]的話，那麼将計數器++，循環過後輸出sum就行了。

錯誤代碼：

#include<bits/stdc++.h>
using namespace std;
int main(){
	while(1){
		int n,sum=0;
		cin>>n;
		if(n==0) break;
		int a[n];
		for(int i=0;i<n;i++) cin>>a[i];
		for(int i=0;i<n;i++)
		  for(int j=i+1;j<n;j++)
		    if(a[i]>a[j])
		      sum++;
		cout<<sum<<endl;
	}
	return 0;
}
           

以上就是我第一次送出的代碼（想都沒有想到是排序“就算标簽上寫着”），結果就寄了“Time Limit Exceeded”

錯誤狀态：

 正确思路：

  經過了這次的逾時，我終于想到了排序，我在想:"連我這個O(nlogn)的時間複雜度都寄了，那麼冒泡等排序就肯定不行了，于是我想到了快排和歸并還有桶"，我是先想效率最快的桶、快排的，但是我實在想不到用快排怎麼實作這道題。

  之後我隻好用歸并了：

        用分治算法，将序列分成兩半，對左邊一半求逆序對數，對右邊一半求逆序對數，然後求左邊一半和右邊一半構成的逆序對數。在求逆序對數的時候要對數列進行歸并排序，在進行歸并排序的同時進行逆序對數的統計。

 求逆序對數代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=20005;
int merge(int a[],int s,int m,int e) {
    vector<int> a1;
    int m1=s,m2=m+1,c=0;
    while(m1<=m&&m2<=e){
        if(a[m1]>a[m2]){
            c+=m-m1+1;
            a1.push_back(a[m2]);
            m2++;
        }
        else{
            a1.push_back(a[m1]);
            m1++;
        }
    }
    while(m1<=m){
        a1.push_back(a[m1]);
        m1++;
    }
    while(m2<=e){
        a1.push_back(a[m2]);
        m2++;
    }
    int k=0;
    for(int i=s;i<=e;i++) a[i]=a1[k++];
    return c;
}
int solve(int a[],int s,int e) {
    if(s>=e) return 0;
    int m=(s+e)/2;
    int l=solve(a,s,m);
    int r=solve(a,m+1,e);
    int l_r=merge(a,s,m,e);
    return l+r+l_r;
}

int main(){
    int n;
    int a[N];
    while(scanf("%d",&n)&&n!=0){
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        int sum=solve(a,0,n-1);
        cout<<sum<<endl;
    }
    return 0;
}

           

 這裡有一個要注意的點就是傳進去的數組是a，a不是一個全局變量，但是遞歸調用之後a的值會改變。

  我之後會繼續講排序的題目（一道比一道難“簡單的我就不講了”）

題目連結：

OpenJudge - 4:求逆序對數

http://dsalgo.openjudge.cn/sort/4/