P1966 [NOIP2013 提高组] 火柴排队

洛谷的一道原题，方法有很多，树状数组以及排序，对刚学树状数组的人来说用排序会比较好理解。

本题最重要的结论就是，要保证两个数组中相同位置的差最小，但是不一定两个数组中数值相同，所以只需要保证相同位置放的数都是当前数组中第i小的，也就是第一个数组里面第i小数和第二个数组中第i的数放的位置要相同，这个地方搞明白之后，只需要找到最小移动次数，这个时候就简单了用归并排序+逆序对即可。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define x first
//#define y second
#define int long long
using namespace std;typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e8 - 3;
const int N = 1e5+ 10;int n, m;typedef struct {int a, b;
}aa; bool cmp(aa a, aa b)
{return a.a < b.a; 
} int s[N], f[N], g[N], sum; void merge_sort(int l, int r)
{if(l >= r) return ;int mid = l + r >> 1;merge_sort(l, mid);merge_sort(mid + 1, r);int i = l, j = mid + 1, k = 0;while(i <= mid && j <= r){if(s[f[i]] <= s[f[j]]) g[k ++] = f[i ++];else{g[k ++] = f[j ++], sum += mid - i + 1;sum %= mod;}}while(i <= mid) g[k ++] = f[i ++];while(j <= r) g[k ++] = f[j ++];for(i = l, j = 0; i <= r; i ++, j ++)f[i] = g[j]; 
}
aa o[N], p[N];
inline void sovle()
{cin >> n;for(int i = 0; i < n; i ++) {cin >> o[i].a;o[i].b = i;}for(int i = 0; i < n; i ++) {cin >> p[i].a;p[i].b = i;}stable_sort(o, o + n, cmp);stable_sort(p, p + n, cmp);for(int i = 0; i < n; i ++)s[i] = p[i].b; // 找出来第二个数组中第i小的数的位置for(int i = 0; i < n; i ++)f[o[i].b] = i; // 找到第一个数组中每个位置都是第几小的merge_sort(0, n - 1);	cout << sum << endl;
}
signed main(void)
{IOS;int t = 1;
//  cin >> t;while(t --) sovle();return 0;
}