火柴排队

Evitagen · 2020-12-28 20:06:29 · 个人记录

学过的归并交给祖宗了

首先，看到这个题，注意最少排序，就很容易联想到逆序对，那么这个题就需要用到归并了。

那么接着，我们可以证明，加入a<b,c<d,那么（a-c）平方+（b-d）平方肯定小于(a-d)平方+(b-c)平方

所以我们这道题就变成了求两组序列（只看序列内数值大小的关系，不看其本身大小），如何挪动使其每组数据大小关系一 一对应

又能证明出来，只挪动一个序列的数就可以实现最短步数。

因此，这道题就变成了，求一组数据，按照另一组数据数据大小排列的编号的逆序对的个数，我们需要用一个c数组来存放这个排序

其中，最关键的是这一步操作：

for(int i=1;i<=n;i++)
        cin>>a[i].ver,a[i].h=i;
    for(int i=1;i<=n;i++)
        cin>>b[i].ver,b[i].h=i;
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++){
        //cout<<a[i].h<<" "<<b[i].h<<endl;
        c[b[i].h]=a[i].h;
    }

其中，h是求其原本的编号，例如：

    2 3 1 4 其对应为1 2 3 4
    3 2 1 4 其对应为1 2 3 4

接着，我们根据本身数值大小排序：

    1 2 3 4，其对应变成3 1 2 4
    1 2 3 4，其对应变成3 2 1 4

这样我们就可以根据a或者b数组，求c数组

c[b[i].h]=a[i].h;

c数组结果为 2 1 3 4

这样，我们就可以愉快的求c的逆序对了！！

接下来是代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int mod=1e8-3;
struct node{
    int ver,h;
}a[N],b[N];
int d[N],c[N];
int n,m;
long long ans=0;
void guibing(int l,int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    guibing(l,mid);
    guibing(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(c[i]>c[j]){
            d[k++]=c[j++];
            ans=(ans+mid-i+1)%mod;
        }
        else
            d[k++]=c[i++];
    }
    while(i<=mid) d[k++]=c[i++];
    while(j<=r) d[k++]=c[j++];
    for(int i=l;i<=r;i++)
        c[i]=d[i];
}
bool cmp(node x,node y)
{
    return x.ver<y.ver;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].ver,a[i].h=i;
    for(int i=1;i<=n;i++)
        cin>>b[i].ver,b[i].h=i;
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++){
        //cout<<a[i].h<<" "<<b[i].h<<endl;
        c[b[i].h]=a[i].h;
    }
    guibing(1,n);
    cout<<ans%mod<<endl;
    return 0;
}