【数据结构】[NOIP2013]火柴排队

题目

要最小化 a[i]-b[i]
也就是说 a 序列第 k 大的元素必须和序列 b 中第kk 大的元素位置必须一样
那么我们我们可以把a b离散化 问题将转化为b序列要交换几次可以令其等于a
假设我们现在有离散化后的序列 a = {4,3,1,2} b = {1,2,4}
我们令 q[a[i]]=b[i] 相当于以a[i]为关键字对序列b[i]排序
若序列a与序列b相等 那么此时q[a[i]]应该等于a[i]的 也就是q[i] = i
那么也就是说如果我们想让序列a与序列b相等 那么我们需要让q升序排列
于是用树状数组求逆序对

顺便复习了一下树状数组求逆序对 Wang.TY平时打的超熟结果没给我讲出来 不过后来几经辗转还是讲出来了

发现以前学的一些东西都忘了

代码如下

#include<iostream> #include<cstdio> #include<cctype> #include<algorithm> using namespace std; #define in = read(); typedef long long ll; typedef unsigned int ui; const ll size = 100000 + 10000; #define lowbit(x) x&-x struct point{ int x,y;}a[size],b[size]; int n; int mod = 99999997,ans; int c[size],f[size]; inline ll read(){ ll num = 0,f = 1; char ch = getchar(); while(!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)){ num = num*10 + ch - '0'; ch = getchar(); } return num*f; } inline bool cmp(point a,point b){ return a.x < b.x; } inline void add(int x){ while(x <= n){ c[x] ++; x += lowbit(x); } } inline int sum(int x){ int ans = 0; while(x){ ans += c[x]; x -= lowbit(x); } return ans; } int main(){ n in; for(register int i=1;i<=n;i++){ a[i].x in; a[i].y = i; } for(register int i=1;i<=n;i++){ b[i].x in; b[i].y = i; } sort(a + 1,a + n + 1,cmp); sort(b + 1,b + n + 1,cmp); for(register int i=1;i<=n;i++) f[a[i].y] = b[i].y; for(register int i=1;i<=n;i++){ add(f[i]); ans = (ans + i - sum(f[i])) % mod; } printf("%d",ans); return 0; } //COYG