彩票网站怎么做系统,简单5步 制作wordpress留言板,专业团队原图,青岛网站定制多少钱洛谷的一道原题#xff0c;方法有很多#xff0c;树状数组以及排序#xff0c;对刚学树状数组的人来说用排序会比较好理解。
本题最重要的结论就是#xff0c;要保证两个数组中相同位置的差最小#xff0c;但是不一定两个数组中数值相同#xff0c;所以只需要保证相同位…洛谷的一道原题方法有很多树状数组以及排序对刚学树状数组的人来说用排序会比较好理解。
本题最重要的结论就是要保证两个数组中相同位置的差最小但是不一定两个数组中数值相同所以只需要保证相同位置放的数都是当前数组中第i小的也就是第一个数组里面第i小数和第二个数组中第i的数放的位置要相同这个地方搞明白之后只需要找到最小移动次数这个时候就简单了用归并排序逆序对即可。 #includebits/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 pairint, 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;
}
