题解 P3656 【[USACO17FEB]Why Did the Cow Cross the Road I P】

· · 题解

看到这道题，我们可以想到2013年提高组火柴排队那道题，这道题其实同理，利用离散化的原理，预处理一个数组然后我们求逆序对就可以 最后求转完逆序对个数最小就可以

题目说两个都可以转，我一开始认为转一个就可以了，后来ly的提醒下发现转一个无论如何也不能满足转第二个产生的情况

比如我们观察这样一个序列

5 3 2 4 1   我们强制对第一行进行编号，1 2 3 4 5

2 1 4 3 5 根据第一行的编号，我们可以生成第二行 3 5 4 2 1

这时候我们去转动第二行，发现只是顺序改变了 比如变成5 4 2 1 3

假如我们转动第一行 3 2 4 1 5 再重新编号 1 2 3 4 5

这时候对应第二行 2 4 3 1 5  我们对比这两个红色的发现他们按照大小重新交换了一遍，相当于每个都减了一 所以只旋转一个是不可以的

1、用树状数组求初始数列的逆序对

2、不停旋转这个序列， 加入5 4 2 1 3 中3换到前面，那么因为交换3而导致的改变就是减去3前面比3大的数加上前面比3小的数就是3交换到前面对答案贡献的改变量

#include<cstdio>
#define N 110000
inline int read(){
    int x=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int s[N],map[N],c[N],a[N],b[N],n;
inline void add(int x){while (x<=n){s[x]++;x+=x&(-x);}}
inline int query(int x){
    int sum=0;
    while (x){
        sum+=s[x];x-=x&(-x);
    }
    return sum;
}
inline long long min(long long x,long long y){return x<y?x:y;}
int main(){
    freopen("3656.in","r",stdin);
    n=read();
    for (int i=1;i<=n;++i) a[i]=read();for (int i=1;i<=n;++i) b[i]=read();
    for (int i=1;i<=n;++i) map[a[i]]=i;
    for (int i=1;i<=n;++i) c[i]=map[b[i]];
    long long ans=0;
    for (int i=1;i<=n;++i)add(c[i]),ans+=(long long)(i)-(long long)query(c[i]);
    long long tmp=ans;
    for (int i=n;i;--i) {
        tmp+=(long long)(c[i]-1);tmp-=(long long) (n-c[i]);
        ans=min(ans,tmp);
    } 
    for (int i=1;i<=n;++i)s[i]=0;
    for (int i=1;i<=n;++i) map[b[i]]=i;
    for (int i=1;i<=n;++i) c[i]=map[a[i]];
    long long ans1=0;
    for (int i=1;i<=n;++i)add(c[i]),ans1+=(long long)(i)-(long long)query(c[i]);
    tmp=ans1;
    for (int i=n;i;--i) {
        tmp+=(long long)(c[i]-1);tmp-=(long long) (n-c[i]);
        ans1=min(ans1,tmp);
    } 
    printf("%lld",min(ans1,ans));
    return 0;
}