Skip to content

11572: 【原1572】逆序对数

题目

题目描述

author: lwher 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1572 # Description 李老板是个非常牛X的人,他买了一排的大楼。每栋大楼有一个不同的高度,这些大楼的高度两两不同,刚好从1~N。

某一天,李老板站在一栋大楼上,突然,他向后看去,看见了许多比他这栋楼矮的楼,他突发奇想,想知道站在每栋楼上向后看,比他当前这栋楼矮的楼数量。

题意简述:给你一个1~N的全排列,求其逆序对个数。即满足Aj>Akj < k的数的对数。

李老板:这题如果不会做,可以随时来找我。

Input Format

第一行有一个整数\(N\) ,代表序列的长度。

接下来 \(N\) 个数代表李老板买的楼的高度序列{X_1,X_2,…,X_N}

Output Format

一个整数,即李老板想要的答案。

注意:答案没有对任何数取模

Sample Input

3 
3 1 2

Sample Output

2

Limits

  • 对于\(40\%\)的数据,N <= 1000。
  • 对于\(100\%\)的数据,N <= 100000。

yyong119's solution

#include <iostream>
using namespace std;
const int MAX_N = 100010;
long long ans;
int n;
int a[MAX_N];

void merge(int l, int r) {

    int mid = (l + r) >> 1, i = l, j = mid + 1, k = l;
    int tmp[MAX_N];
    while (i <= mid && j <= r) {
        if (a[i] < a[j]) tmp[k++] = a[i++];
        else {
            ans += mid - i + 1;
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int i = l; i <= r; ++i) a[i] = tmp[i];
}

void mergesort(int l, int r) {

    if (l == r) return;
    int mid = (l + r) >> 1;
    mergesort(l, mid);
    mergesort(mid + 1, r);
    merge(l, r);
}

int main() {

    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    mergesort(1, n);
    cout << ans << endl;
    return 0;
}