[基本練習][枚舉]OI練習題： 排序工作量 sortt

【問題描述】

Sort公司是一個專門爲人們提供排序服務的公司，該公司的宗旨是：“順序是最美麗的”。他們的工作是通過一系列移動，將某些物品按順序擺好。他們的服務是通過工作量來計算的，即移動東西的次數。所以，在工作前必須先考察工作量，以便向用戶提出收費數目。

用戶並不需要知道精確的移動次數，實質上，大多數人都是憑感覺來認定這一列物品的混亂程度，根據Sort公司的經驗，人們一般是根據“逆序對”的數目多少來稱呼這一序列的混亂程度。假設我們將序列中第I件物品的參數定義爲A[I]，那麼，排序就是指將A數組從小到大排序。所謂“逆序對”是指目前A[1..N]中元素各不相同，若I<J且A[I]>A[j]，則[I,J]就爲一個“逆序對”。

例如，數組<3,1,4,5,2>的“逆序對”有<3,1>,<3,2>,<4,2>,<5,2>，共4個(如圖所示)。

  請你爲 Sort 公司做一個程序，在儘量短的時間內，統計出“逆序對”的數目。 

【輸入格式】

文件的第一行爲一個整數N（1<=N<=10000）。

文件的第二行爲N個實數。

【輸出格式】

文件共一行，爲“逆序對”的數目。

【輸入輸出樣例】

輸入：

sortt.in

5

3 1 4 5 2

輸入：

sortt.out

4

【分析】

直接枚舉即可。時間複雜度 O（n^2），不會超時。

【代碼】

#include <cstdio>
using namespace std;
double M[10001];
int N;
int T;

int main()
{
    freopen("sortt.in","r",stdin);
    freopen("sortt.out","w",stdout);
    scanf("%d",&N);
    for (int i=1;i<=N;i++)
        scanf("%lf",&M[i]);
    for (int i=1;i<=N-1;i++)
        for (int j=i+1;j<=N;j++)
            if(M[i]>M[j])
                T++;
    printf("%d\n",T);
    return 0;
}