P1966 火柴排队【逆序对】

洛谷P1966

题目大意

给两个序列 $a_i,b_i$ai​,bi​ ，可以交换相邻两数，要求满足 ${\sum }_{i=1}^n(a_i-b_i{)}^2$∑i=1n​(ai​−bi​)2 最小 ，求最少的交换次数

题目分析

${\sum }_{i=1}^n(a_i-b_i{)}^2$∑i=1n​(ai​−bi​)2 最小
只需满足，大的和大的配对，小的和小的配对
找到 $b_i$bi​序列中的数对应 $a_i$ai​序列中的数的位置。
则求出了最终的变换位置。由于只能相邻交换
对位置求逆序对即可

代码详解

#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
typedef pair<ll,int> PLI;
int n;
const int maxn = 1e6+50;
PLI a[maxn],b[maxn];
ll c[maxn];
ll tmp[maxn];
ll ans=0;
const int mod = 99999997;
void merge(int l1,int r1,int l2,int r2)
{
    int i=l1;
    int j=l2;
    int id=l1;
    while(i<=r1&&j<=r2){
        if(c[i]<=c[j]) {
            tmp[id++] = c[i];
            i++;
        }
        else {
            ans =(ans+ (r1-i+1))%mod; 
            tmp[id++] = c[j];
            j++;
        }
    }
    while(i<=r1)  tmp[id++]=c[i++];
    while(j<=r2)  tmp[id++]=c[j++];
    for(int i=l1;i<=r2;i++)  c[i]=tmp[i];
}
void mergesort(int l,int r)
{
    if(l<r)
    {
        int mid = (r+l)/2;
        mergesort(l,mid);
        mergesort(mid+1,r);
        merge(l,mid,mid+1,r);
    }
}
int main()
{
    scanf("%d",&n);
    //对两行数据排序
    rep(i,1,n) {scanf("%lld",&a[i].fi);a[i].se=i;}
    rep(i,1,n) {scanf("%lld",&b[i].fi);b[i].se=i;}
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    //找到第二行元素所匹配的第一行元素的位置
    rep(i,1,n){
        int t = b[i].se;
        c[t] = a[i].se;
    }
    //对c[i]数组求逆序对
    mergesort(1,n);
    printf("%lld\n",ans);
    return 0;
} 

/* 4 2 3 1 4 3 2 1 4 */