POJ-1804

求逆序对数

输入描述:

The first line contains the number of scenarios.
For every scenario, you are given a line containing first the length N (1 <= N <= 1000) of the sequence,followed by the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks.

输出描述:

Start the output for every scenario with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence. Terminate the output for the scenario with a blank line.

示例1
输入

4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0

输出

Scenario #1:
3

Scenario #2:
0

Scenario #3:
5

Scenario #4:
0

POJ_1804_merge_sort.cppview raw

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 1010;
int a[N], tmp[N];
int n;

int merge_sort(int L, int R){
    if(L>=R) return 0;
    int mid = L+R>>1;
    int res = merge_sort(L, mid) + merge_sort(mid+1, R);
    int l = L, r=mid+1, k = 0;
    while(l<=mid && r<=R){
        if(a[l]<=a[r]) tmp[k++] = a[l++];
        else {
            tmp[k++] = a[r++];
            res += mid-l+1;
        }
    }
    while(l<=mid) tmp[k++] = a[l++];
    while(r<=R) tmp[k++] = a[r++];
    for(int i=L, j=0; i<=R; i++, j++) a[i] = tmp[j];
    return res;
}

int main(){
    int T;
    scanf("%d",&T);
    for(int i=1;i<=T;i++){
        memset(a, 0, sizeof a);
        scanf("%d", &n);
        for(int i=0;i<n;i++) scanf("%d", &a[i]);
        int res = merge_sort(0, n-1);
        printf("Scenario #%d:\n%d\n\n", i, res);
    }
    return 0;
}

POJ_1804_seg_tree.cppview raw

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1010;
int a[N], bin[N];
int n;
int sum[N];

void update(int x){
    sum[x] = sum[x*2] + sum[x*2+1];
}

void build(int l,int r, int x){
    if(l==r){
        sum[x] = 0; //mistake
        return;
    }
    int mid = l+r>>1;
    build(l, mid, x<<1);
    build(mid+1, r, x<<1|1);
    update(x);
}


int query(int A, int B, int l, int r, int x){
    if(A<=l && B>=r) return sum[x];
    int mid = l+r>>1;
    int ans = 0;
    if(A<=mid) ans += query(A, B, l, mid, x<<1);
    if(B>mid) ans += query(A, B, mid+1, r, x<<1|1);
    return ans;
}

void change(int pos, int v, int l, int r, int x){
    if(l==r) {
        sum[x]+= v;
        return;
    }
    int mid = l+r>>1;
    if(pos <=mid) change(pos, v, l, mid, x<<1);
    else change(pos, v, mid+1, r, x<<1|1);
    update(x);
}

int main(){
    int T;
    scanf("%d",&T);
    for(int i=1;i<=T;i++){
        memset(a, 0, sizeof a);
        memset(bin, 0, sizeof bin);
        memset(sum, 0, sizeof sum);
        scanf("%d", &n);
        int cnt = 0;
        for(int i=1;i<=n;i++) {
            scanf("%d", &a[i]);
            bin[++cnt] = a[i];
        }
        sort(bin+1, bin+1+cnt);
        cnt = unique(bin+1, bin+1+cnt) - bin-1;
        for(int i=1;i<=n;i++) {
            a[i] = lower_bound(bin + 1, bin + 1 + cnt, a[i]) - bin;
        }

        build(1, cnt, 1);
        int res = 0;
        for(int i=1;i<=n;i++){
            res += query(a[i]+1, cnt, 1, n, 1);
            change(a[i], 1, 1, n, 1);
        }

        printf("Scenario #%d:\n%d\n\n", i, res);
    }
    return 0;
}