P8613 [蓝桥杯 2014 省 B] 小朋友排队

因为相邻两个数字交换，每次只能减少一个逆序对数量，所以这道题最终的交换次数就等于原序列当中逆序对的数量。

但是因为每个数字的交换代价会随着交换次数而增加，所以虽然我们知道Σ数字交换次数 = 逆序对数量，我们也不能按照传统的逆序对数量统计方式直接计算，这样子会导致我们只知道最终的交换次数，但不知道每个数字的权值。

因此，我们要变相统计逆序对数量，针对每个数字统计他需要进行交换的次数。

本题代码：

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

const int N = 100005;

struct mytype{
    int v, cnt;
    bool operator < (const mytype &tmp) const
    {
        return v < tmp.v;
    }
} a[N], tmp[N];

inline int read()
{
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')
        ch = getchar();
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}

int n;

void mergesort(int l, int r)
{
    if(l == r) return;
    int mid = l + r >> 1;
    mergesort(l, mid); 
    mergesort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r)
    {
        if(a[i].v <= a[j].v) 
        {
            a[i].cnt += j - mid - 1;
            tmp[k++] = a[i++];
        }
        else 
        {
            a[j].cnt += mid - i + 1;
            tmp[k++] = a[j++];
        }
    }
    while(i <= mid)
    {
        a[i].cnt += r - mid;
        tmp[k++] = a[i++];
    }
    while(j <= r) tmp[k++] = a[j++];
    for(int t = l; t <= r; t++)
        a[t] = tmp[t];
}

int main()
{
    n = read();
    for(int i = 1; i <= n; i++)
    {
        a[i].v = read();
    }
    mergesort(1, n);
    long long ans = 0;
    for(int i = 1; i <= n; i++)
        ans += (long long) a[i].cnt * (a[i].cnt + 1) / 2;
    cout << ans << endl;
    system("pause");
    return 0;
}

可以与“用归并排序统计逆序对”的代码进行比较，加深理解：

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,a[N];
int tmp[N];
void sort(int l,int r)
{
    if(l==r) return ;
    int mid=l+r>>1;
    sort(l,mid);sort(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r) 
    {
        if(a[i]<=a[j]) tmp[k++]=a[i++];
        else 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];
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(1,n);
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}

在统计逆序对的时候，我们只需要在(a[i]<=a[j])或者(a[i]>a[j])一种情况下进行统计，因为一个逆序对虽然与两个数字有关，但是我们在涉及到其中任何一个数字时，都能算上这个逆序对。

但是在这道题的代码当中，我们在这两种情况里就都需要进行统计，因为一次交换对于它所涉及的两个数字而言，它们的权值都会增加一。