考点
题解
见思路
思路
$$
\sum{\left( a_i-b_i \right) ^2}\rightarrow \sum{{a_i}^2+{b_i}^2-2a_ib_i}\rightarrow \underset{A}{\underbrace{\sum{{a_i}^2+{b_i}^2}}}-\underset{B}{\underbrace{2\sum{a_ib_i}}}
$$
由上述式子展开发现，A式其实是不变的；要让整体最小，a、b数组对应位置的元素乘积就要最大。
由排序不等式可知，若把两数组排序后，对于每个k，将第k小的ak元素与第k小的bk元素配对可得到最大乘积。
通俗点说，ai在a数组的大小排名应该等于bi在b数组的大小排名。
数组转换法（必须掌握）
由于是比较排名，先对a、b两数组进行离散化，得到如下数据：
a = {1, 3, 4, 2, 5}，b = {3, 2, 5, 4, 1}
此时要求数组a转换为数组b需要交换元素的次数。
正常情况下，数组通过下面的映射规律后再排序（只是平常没有感觉）
如果此时将数组b作为新的映射规律后：
那么数组a在b的映射下，就会变成a = {1 -> 5, 3 -> 1, 4 -> 4, 2 -> 2, 5 -> 3}，
即a = {5, 1, 4, 2, 3}
接下来就是求此时的数组a排序的交换元素次数，直接累计所有元素的逆序对个数即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 50, mod = 1e8 - 3;
int n, a[maxn], b[maxn], mp[maxn];
int atot, btot, da[maxn], db[maxn];
ll ans, bit[maxn];
int lowbit(int x) { return x & -x; }
void add(int x, int v) {
while (x <= n) bit[x] += v, x += lowbit(x);
}
ll query(int x) {
ll res = 0;
while (x > 0) res += bit[x], x -= lowbit(x);
return res;
}
void dis() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i], da[i] = a[i];
for (int i = 1; i <= n; ++i) cin >> b[i], db[i] = b[i];
sort(da + 1, da + 1 + n), sort(db + 1, db + 1 + n);
atot = unique(da + 1, da + 1 + n) - 1 - da;
btot = unique(db + 1, db + 1 + n) - 1 - db;
for (int i = 1; i <= n; ++i) {
a[i] = lower_bound(da + 1, da + 1 + atot, a[i]) - da;
b[i] = lower_bound(db + 1, db + 1 + btot, b[i]) - db;
}
for (int i = 1; i <= n; ++i) mp[b[i]] = i;
for (int i = 1; i <= n; ++i) a[i] = mp[a[i]];
}
int main() {
dis();
ll ans = 0;
for (int i = n; i >= 1; --i) {
ans = (ans + query(a[i] - 1)) % mod;
add(a[i], 1);
}
cout << ans;
return 0;
}
|
取巧
本题可以不用像上面一样更改映射，保持默认的映射即可：
用结构体数组a、b分别记录原a、b数组每个元素的值val以及元素的下标pos，
结构体数组a、b分别对val排序，该操作可以理解为，以默认映射为标准进行对齐，
对齐之后，ai和bi的val在各自原数组内的排名都是一致的；
为满足题意要求，按道理ai和bi的pos也应该一样；如果不一样，须让a[i].pos朝b[i].pos对齐，
那么设新的映射数组mp[b[i].pos] = a[i].pos，mp排序时的逆序对总数即为答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 50, mod = 1e8 - 3;
int n, mp[maxn], t[maxn];
ll ans;
struct node {
int val_, pos_;
bool operator<(node &x) { return val_ < x.val_; }
} a[maxn], b[maxn];
void merge(int l, int r) {
if (l == r) return;
int i = l, j = l, mid = (l + r) / 2, k = mid + 1;
merge(l, mid), merge(mid + 1, r);
while (j <= mid && k <= r) {
if (mp[j] <= mp[k]) {
t[i++] = mp[j++];
} else {
t[i++] = mp[k++];
ans = (ans + mid - j + 1) % mod;
}
}
while (j <= mid) t[i++] = mp[j++];
while (k <= r) t[i++] = mp[k++];
for (i = l; i <= r; ++i) mp[i] = t[i];
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i].val_, a[i].pos_ = i;
for (int i = 1; i <= n; ++i) cin >> b[i].val_, b[i].pos_ = i;
sort(a + 1, a + 1 + n), sort(b + 1, b + 1 + n);
for (int i = 1; i <= n; ++i) mp[b[i].pos_] = a[i].pos_;
merge(1, n);
cout << ans;
return 0;
}
|