题目
解法
这道题实际上是一类问题:给你两个序列 (a(n) b(n)),问最少花费几步可以将(a(n))变成(b(n))。
如何做这种问题呢?
我们考虑这个步数要最小实际上是什么,就是讲优先级一样的放在两个序列的相同位置,并且尽量让每一个数移动的位置最少。
所以我们需要将(a(n) 和 b(n))按照优先级排序。
那排序后又怎么做呢?
我们考虑构建一个新的数组 (c(n)),其中 ( c[a[i],id] = b[i].id )。
然后要让 (a(n)=b(n)) 实际上就是要让(c[i]=i) 也就是要让b数组中第i个数和a数组中第i个数在同一个位置。
那么这就转化成了求解逆序对的数量了。
代码
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <cctype> #include <vector> #define INF 2139062143 #define MAX 0x7ffffffffffffff #define del(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; template<typename T> inline void read(T&x) { x=0;T k=1;char c=getchar(); while(!isdigit(c)){if(c=='-')k=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=k; } const int maxn=1e5+15; const int mod=99999997; int n; int temp[maxn]; struct node { int h,id; bool operator < (const node& x) const { return h==x.h?id<x.id:h<x.h; } }a[maxn],b[maxn]; #define lowbits(x) (x&(-x)) ll c[maxn]; inline void add(int pos,int k) { for(int i=pos;i<=n;i+=lowbits(i)) c[i]+=k; } inline ll query(int pos) { ll re=0; for(int i=pos;i;i-=lowbits(i)) re+=c[i]; return re; } int main() { read(n); for(int i=1;i<=n;i++) read(a[i].h),a[i].id=i; for(int i=1;i<=n;i++) read(b[i].h),b[i].id=i; sort(a+1,a+1+n);sort(b+1,b+1+n); for(int i=1;i<=n;i++) temp[b[i].id]=a[i].id; ll ans=0; for(int i=1;i<=n;i++) { ll k=query(temp[i]); ans+=i-1-k; add(temp[i],1ll); } printf("%lld ",ans%mod); return 0; }