题目描述
涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：
Σ(\(a_i\) - \(b_i\))²
其中a_i表示第一列火柴中第 i 个火柴的高度，b_i表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997取模的结果。
输入输出格式
输入格式：
共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。
输出格式：
一个整数，表示最少交换次数对99,999,997取模的结果。
输入输出样例
输入样例#1： 复制
4 2 3 1 4 3 2 1 4
输出样例#1： 复制
1
输入样例#2： 复制
4 1 3 4 2 1 7 2 4
输出样例#2： 复制
2
说明
【输入输出样例说明1】
最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2根火柴。
【输入输出样例说明2】
最小距离是 10，最少需要交换 2次，比如：交换第 1 列的中间 2根火柴的位置，再交换第 2 列中后 2 根火柴的位置。
【数据范围】
对于 10%的数据， 1 ≤ n ≤ 10；
对于 30%的数据，1 ≤ n ≤ 100；
对于 60%的数据，1 ≤ n ≤ 1,000；
对于 100%的数据，1 ≤ n ≤ 100,000, 0≤火柴高度≤ maxlongint
主要思路 ：权值线段树求逆序对
实际上就是把两个数组提前标上序号然后求逆序对个数
证明我就不说了，很多大佬的证明比我的证明严密很多
这里主要是求逆序对的方法
我用的是权值线段树来求逆序对
我们把线段树维护的区间上的每个点作为权值，维护的值也就是这些数据中在某个范围内的数的个数
和树状数组的方法有点类似，（我偏不用树状数组和归并排序因为都不会
这样实际上是要把这个数组离散化才能压到线段树里的，但是这道题维护的数组的值就是1 ~ n的，所以不需要离散化
code ：
#1 ：普通线段树 ：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
using namespace std;
#define go(i, j, n, k) for(int i = j; i <= n; i += k)
#define fo(i, j, n, k) for(int i = j; i >= n; i -= k)
#define rep(i, x) for(int i = h[x]; i; i = e[i].nxt)
#define mn 100010
#define inf 1 << 30
#define ll long long
#define mod 99999997
#define root 0, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
inline int read() {
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x * f;
}
inline void fre() {
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
}
struct node{
int x, pos;
node(int _x = 0, int _pos = 0) : x(_x), pos(_pos) {}
}a[mn], b[mn];
int z[mn << 2], c[mn], n;
ll ans = 0;
inline void update(int rt) {
z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
inline void build(int l, int r, int rt) {
if(l == r) { z[rt] = 0; return; }
int m = (l + r) >> 1;
build(lson), build(rson), update(rt);
}
inline void modify(int l, int r, int rt, int now) {
if(l == r) { z[rt]++; return; }
int m = (l + r) >> 1;
if(now <= m) modify(lson, now);
else modify(rson, now);
update(rt);
}
inline int query(int l, int r, int rt, int nowl, int nowr) {
if(nowl <= l && r <= nowr) { return z[rt]; }
int m = (l + r) >> 1;
if(nowl <= m) {
if(m < nowr) return query(lson, nowl, nowr) + query(rson, nowl, nowr);
else return query(lson, nowl, nowr);
} else return query(rson, nowl, nowr);
}
inline bool cmp (node a, node b) { return a.x < b.x; }
inline void debug() {
go(i, 1, n, 1) printf("%d%c", c[i], (i != n) ? ' ' : '\n');
}
int main() {
//fre();
n = read();
go(i, 1, n, 1) a[i].x = read(), a[i].pos = i;
go(i, 1, n, 1) b[i].x = read(), b[i].pos = i;
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + n + 1, cmp);
go(i, 1, n, 1) c[a[i].pos] = b[i].pos;
build(root);
fo(i, n, 1, 1) {
ans = (ans + query(root, 0, c[i] - 1)) % mod;
modify(root, c[i]);
}
cout << ans << "\n";
return 0;
} #2 : zkw线段树
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
using namespace std;
#define go(i, j, n, k) for(int i = j; i <= n; i += k)
#define fo(i, j, n, k) for(int i = j; i >= n; i -= k)
#define rep(i, x) for(int i = h[x]; i; i = e[i].nxt)
#define mn 100010
#define inf 1 << 30
#define ll long long
#define mod 99999997
#define root 0, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
inline int read() {
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x * f;
}
inline void fre() {
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
}
struct node{
int x, pos;
node(int _x = 0, int _pos = 0) : x(_x), pos(_pos) {}
}a[mn], b[mn];
int z[mn << 2], c[mn], n, M;
ll ans = 0;
inline void update(int rt) {
z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
inline void build() {
for(M = 1; M < n + 2; M <<= 1);
go(i, M, M + n + 2, 1) z[i] = 0;
fo(i, M, 1, 1) update(i);
}
inline void modify(int now) {
for(z[now += M]++, now >>= 1; now; now >>= 1) update(now);
}
inline int query(int l, int r) {
int ans = 0;
for(--l += M, ++r += M; l ^ r ^ 1; l >>= 1, r >>= 1) {
if(~l & 1) ans += z[l ^ 1];
if(r & 1) ans += z[r ^ 1];
}
return ans;
}
inline bool cmp (node a, node b) { return a.x < b.x; }
inline void debug() {
go(i, 1, n, 1) printf("%d%c", c[i], (i != n) ? ' ' : '\n');
}
int main() {
//fre();
n = read();
go(i, 1, n, 1) a[i].x = read(), a[i].pos = i;
go(i, 1, n, 1) b[i].x = read(), b[i].pos = i;
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + n + 1, cmp);
go(i, 1, n, 1) c[a[i].pos] = b[i].pos;
build();
// debug();
fo(i, n, 1, 1) {
ans = (ans + query(1, c[i] - 1)) % mod;
modify(c[i]);
}
cout << ans << "\n";
return 0;
} #3 : （接地气的）树状数组（我还是写了）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
using namespace std;
#define go(i, j, n, k) for(int i = j; i <= n; i += k)
#define fo(i, j, n, k) for(int i = j; i >= n; i -= k)
#define rep(i, x) for(int i = h[x]; i; i = e[i].nxt)
#define mn 100010
#define inf 1 << 30
#define ll long long
#define mod 99999997
#define root 0, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
inline int read() {
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x * f;
}
inline void fre() {
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
}
struct node{
int x, pos;
node(int _x = 0, int _pos = 0) : x(_x), pos(_pos) {}
}a[mn], b[mn];
int z[mn], c[mn], n, M;
inline int lb(int x) { return x & -x; }
inline void modify(int now, int v) { for(int i = now; i <= n; i += lb(i)) z[i] += v; }
inline int query(int x) { int ans = 0; for(int i = x; i; i -= lb(i)) ans += z[i]; return ans; }
ll ans = 0;
inline bool cmp (node a, node b) { return a.x < b.x; }
inline void debug() {
go(i, 1, n, 1) printf("%d%c", c[i], (i != n) ? ' ' : '\n');
}
int main() {
//fre();
n = read();
go(i, 1, n, 1) a[i].x = read(), a[i].pos = i;
go(i, 1, n, 1) b[i].x = read(), b[i].pos = i;
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + n + 1, cmp);
go(i, 1, n, 1) c[a[i].pos] = b[i].pos;
// debug();
fo(i, n, 1, 1) {
ans = (ans + query(c[i] - 1)) % mod;
modify(c[i], 1);
}
cout << ans << "\n";
return 0;
}
京公网安备 11010502036488号