归并排序求逆序数

浏览数：20 / 时间：2015年06月08日

A - Frosh Week

Time Limit:8000MS Memory Limit:0KB 64bit IO Format:%lld & %llu

Submit Status Practice UVA 11858

Appoint description:

Description

Problem E: Frosh Week

During Frosh Week, students play various fun games to get to know each other and compete against other teams. In one such game, all the frosh on a team stand in a line, and are then asked to arrange themselves according to some criterion, such as their height, their birth date, or their student number. This rearrangement of the line must be accomplished only by successively swapping pairs of consecutive students. The team that finishes fastest wins. Thus, in order to win, you would like to minimize the number of swaps required.

Input Specification

Input contains several test cases. For each test case, the first line of input contains one positive integer n, the number of students on the team, which will be no more than one million. The following n lines each contain one integer, the student number of each student on the team. No student number will appear more than once.

Sample Input

Output Specification

For each test case, output a line containing the minimum number of swaps required to arrange the students in increasing order by student number.

Output for Sample Input

Ond?ej Lhoták

#include <stdio.h>  
  
#define N  1000001  
  
typedef long long LL;  
  
int n;  
int num[N], tmp[N];  
  
int input()  
{  
    if (scanf("%d", &n) != 1) return 0;  
      
    int i;  
    for (i = 0; i < n; i++) {  
        scanf("%d", &num[i]);  
    }  
    return 1;  
}  
  
LL mergesort(int l, int r, int a[])  
{  
    if (l >= r) return 0;  
      
    int m = (l + r) >> 1;  
    LL s1 = mergesort(l, m, a);  
    LL s2 = mergesort(m + 1, r, a);  
    LL sum = s1 + s2;  
      
    int p = l, q = m + 1;  
    int k = l;  
      
    while (p <= m || q <= r) {  
        if (p > m || (q <= r && a[p] > a[q])) {  
            tmp[k++] = a[q++];  
            sum += m + 1 - p;  
        } else {  
            tmp[k++] = a[p++];  
        }  
    }  
      
    int i;  
    for (i = l; i <= r; i++) {  
        a[i] = tmp[i];  
    }  
      
    return sum;  
}  
  
void solve()  
{  
    LL ans = mergesort(0, n - 1, num);  
    printf("%lld\n", ans);  
}  
  
int main()  
{  
    #ifndef ONLINE_JUDGE  
        freopen("d:\\OJ\\uva_in.txt", "r", stdin);  
    #endif  
      
    while (input()) {  
        solve();  
    }  
    return 0;  
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

归并排序求逆序数