51nod 1574 排列转换(猜结论)

分析

猜了一下结论,居然对了..........具体操作是:假设排列s是1,2,3,...,nk为排列p中最大的没有放到正确位置的数,k的位置为posk的右边一定有一个数x<=pos(因为<=pos的数有pos个,不可能全挤在pos-1个位置里)交换k和x,两个数都离目标更近了且没有走远路.重复这个步骤

猜了两次结论然后就对了？？？

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

int n,x;

int a[200200],b[200200];

ll ans;

int main()

{

    cin>>n;

    F(i,1,n) cin>>x,a[x]=i;

    F(i,1,n) cin>>x,b[x]=i;

    F(i,1,n)

    {

        ans+=abs(a[i]-b[i]);

    }

    cout<<ans/2<<endl;

    return 0;

}

巴特西

51nod 1574 排列转换(猜结论)

最新文章

热门文章