70285 - CSP-S第一轮同测模拟卷1阅读程序2
统计题目(材料题)
01 #include <iostream>
02 #include <algorithm>
03 using namespace std;
04 const int MAXN = 100005;
05
06 struct ele {
07 int i;
08 int val;
09 bool operator < (ele e2) const {
10 return val < e2.val;
11 }
12 } a[MAXN], b[MAXN];
13 int c[MAXN];
14 int d[MAXN];
15 long long ans = 0;
16
17 void solve(int left, int right) {
18 if (left == right)
19 return;
20 int mid = (left + right) / 2;
21 solve(left, mid);
22 solve(mid + 1, right);
23 for (int i = left, i1 = left, i2 = mid + 1; i1 <= mid || i2 <= right; i++) {
24 if (i2 > right || (i1 <= mid && c[i1] <= c[i2])) {
25 d[i] = c[i1];
26 i1++;
27 ans += i2 - mid - 1;
28 } else {
29 d[i] = c[i2];
30 i2++;
31 }
32 }
33 for (int i = left; i <= right; i++)
34 c[i] = d[i];
35 }
36
37 int main() {
38 int n;
39 cin >> n;
40 for (int i = 1; i <= n; i++) {
41 cin >> a[i].val;
42 a[i].i = i;
43 }
44 for (int i = 1; i <= n; i++) {
45 cin >> b[i].val;
46 b[i].i = i;
47 }
48 sort(a + 1, a + n + 1);
49 sort(b + 1, b + n + 1);
50 for (int i = 1; i <= n; i++)
51 c[a[i].i] = b[i].i;
52 solve(1, n);
53 cout << ans;
54 return 0;
55 }
关注我们
