洛谷P1966 火柴排队

@Pelom  September 26, 2019

题意

给出数列$a,b$,可交换各个数列中相邻的数,求最小的交换次数,使得$$\sum(a_i-b_i)^2$$最小,答案对$99999997$取模

数据范围:$1 \le n \le 1000000$

题解

对目标式化简

$$ \begin{aligned} \sum(a_i-b_i)^2 &= \sum(a_i^2-2a_ib_i+b_i^2) \\ &= \sum a_i^2 + \sum b_i^2 - 2\sum a_ib_i \end{aligned} $$

前两项的值为定值,对于第$3$项,为了最大,我们希望$a_i,b_i$分别在数列$a,b$的次序相同(即排序后$a_i$与$b_i$位于两个数列的同一位置,但我们显然没有必要将两个数列都进行排序,只需使两个数列的同一位置上的次序相同),因此我们将数列$a,b$离散化,然后使数列$b$与$a$相同,求$b$交换的次数(逆序对个数)即可,但是如何使数列$b$与$a$相同呢?
记$c[a[i]]=b[i]$,对数组$c$求逆序对,在求得逆序对之后,数组$c$会变得有序,即$c[i]=i$,回去看数组$c$的定义,则有$c[a[i]]=a[i]=b[i]$
求逆序对可用归并排序或树状数组

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1000000+10;
const int mod=99999997;
int n;
int T[N],c[N];
int ans;
struct node{
    int h,p;
    inline bool operator < (const node& x){
        return h<x.h;
    }
} a[N],b[N];
inline int lowbit(int x){
    return x&-x;
}
inline void update(int p,int v){
    for(;p<=n;p+=lowbit(p))
        T[p]+=v;
}
inline int query(int p){
    int res=0;
    for(;p;p-=lowbit(p))
        res+=T[p];
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].h);
        a[i].p=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i].h);
        b[i].p=i;
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
        c[a[i].p]=b[i].p;
    for(int i=n;i;i--){
        (ans+=query(c[i]-1))%=mod;
        update(c[i],1);
    }
    printf("%d",ans);
    return 0;
}

添加新评论