ACM ICPC 2011–2012, NEERC, Northern Subregional Contest J. John’s Inversions（合并排序求逆序数对数）

本文链接：https://blog.csdn.net/CriminalCode/article/details/48057659

这篇博客介绍了如何运用归并排序算法解决ACM ICPC 2011-2012年北方次区域竞赛中的一道题目，该题目涉及计算逆序数对。博主通过分析得出，当一种颜色的数字按顺序排列且相同颜色对应另一种颜色也按顺序排列时，逆序数对最少。为了在数量级较大的情况下有效计算，博主利用合并排序的原理，计算每个数字前面大于它的数字数量，最后累加得到答案。提供的代码实现了这一方法，并在主函数中读取输入数据，进行排序和计算。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目链接：http://codeforces.com/gym/100609/attachments

题目大意：有n张牌，每张牌有红色和蓝色两面，两面分别写了一些数字，同种颜色的任意两个数字若排在前面的数字比排在后面的数字大就叫做一对逆序数。求怎样排序得到的逆序数对最少。

解题思路：其中一种颜色的数字是顺序且这种颜色数字相同时对应的另一种颜色的数字是顺序时得到的逆序数对数最少。难点在于求逆序数对数。因为数量很大O(n^2)复杂度不能满足，这里根据合并排序的原理求解每个数字前面有多少个比它大的数字，最后加起来就是答案。合并排序复杂度是O（n）。

代码如下：

#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std; 
const int maxn=100005;
ll ans;
int data[maxn];
int n;
struct node
{
    int a,b;
}s[maxn];
ll cmp(node p,node q) 
{
    if(p.a==q.a)
        return p.b<q.b;
    else
        return p.a<q.a;
}
void Merge(int l,int mid,int r)  //合并
{
    int k=0,i=l,j=mid+1;   
    int tar[maxn];    //临时数组用来暂时存储有序数列
    while(i<=mid&&j<=r)   //把两组有序数列a[l]...a[mid]和a[mid+1]...a[r]合并成一组有序数列tar[0]...tar[r-l+1]
    {
        if(data[i]<=data[j])   //把小的数字给数组tar[]
            tar[k++]=data[i++];
        else                  
        {
            tar[k++]=data[j++];
            ans+=mid-i+1;     //关键点，在后一组里有最小的数字，说明前一组序列里剩下的数字都比这个数字大，而且前一组数列里的每个数字都在后一组数列的前面
        }
    }
    while(i<=mid)
        tar[k++]=data[i++];
    while(j<=r)
        tar[k++]=data[j++];
    for(k=0,i=l;i<=r;)       //把有序数列复制给data[l]..data[r]，data[]值是改变的，变成有序的，保证合并上一层有序数列时满足条件
        data[i++]=tar[k++];
}
void MergeSort(int l,int r)  //排序
{
    if(l<r)
    {
        int mid=(l+r)/2;
        MergeSort(l,mid);
        MergeSort(mid+1,r);
        Merge(l,mid,r);
    }
}
int main(void)
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(data,0,sizeof(data));
        for (int i=0;i<n;i++)
            scanf("%d%d",&s[i].a,&s[i].b);
        sort(s,s+n,cmp);
        for(int i=0;i<n;i++)
            data[i]=s[i].b; 
        ans=0;
        MergeSort(0,n-1);
        printf("%I64d\n",ans);
    }
}