[NOIP2013 提高组] 火柴排队
题目描述
涵涵有两盒火柴,每盒装有 $n$ 根火柴,每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列, 同一列火柴的高度互不相同, 两列火柴之间的距离定义为:$\sum (a_i-b_i)^2$。
其中 $a_i$ 表示第一列火柴中第 $i$ 个火柴的高度,$b_i$ 表示第二列火柴中第 $i$ 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数对 $10^8-3$ 取模的结果。
对于 $100%$ 的数据,$1 \leq n \leq 10^5$,$0 \leq$ 火柴高度 $< 2^{31}$。
分析
依题意模拟即可
注意到,可以随意对两个数组进行排序。
分析可知若需要 $\sum (a_i-b_i)^2$ 最小,可以让两数组都有序(单调性相同)。
如果考虑对两个数组都进行若干次交换,情况太复杂了。
发现这完全可以转化为只对其中一个数组的交换(比如说 $b_i$)。
又注意到,这两个数组的对应位置是相对独立的,那么有以下做法:
- 对 $b_i$ 进行若干次交换,使得 $b_i$ 作为第 $k$ 大的数与 $a_i$ 同样也是第 $k$ 大的数相对应。
- (第 $k$ 大指相对于各自的数组)
但是 $a_i$ 不是有序的,这是如果对 $b_i$ 进行排序,会很难处理,考虑进行转化。
假设 $a_i$ 一开始就是有序的,那么只需要对 $b_i$ 从小到大排序即可。
答案就是 $b_i$ 中逆序对的数量,用树状数组维护。
如何进行转化呢? 需要重新指定数字间的大小关系。
关系是什么呢? 从 $a_i$ 来。
如果认为 $a_i$ 是第 $i$ 小的数,就可以以此对 $b_i$ 进行排序了。
不要忘了进行离散化!(把值域缩到 $[1, n]$)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int mod = (114514+114514)*(-11+451-4)+114514+114*51*4+114*51+4+1/1-4+51*4;
int n, ans;
int a[N], b[N], to[N];
struct bitree{
int c[N], res;
inline int lb(int x) { return x & (-x); }
inline void add(int x, int v){
for (; x <= n; x += lb(x))
c[x] += v;
}
inline int find(int x){
for (res = 0; x; x -= lb(x))
res += c[x];
return res;
}
inline int find(int x, int y){
return find(y) - find(x - 1);
}
}tr;
map<int, int> mpa, mpb;
signed main(){
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], mpa[a[i]] = i;
for (int i = 1; i <= n; i++)
cin >> b[i], mpb[b[i]] = i;
sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + n);
for (int i = 1; i <= n; i++)
to[mpa[a[i]]] = mpb[b[i]];
for (int i = 1; i <= n; i++){
ans = (ans + tr.find(n - to[i])) % mod;
tr.add(n - to[i] + 1, 1);
}
cout << ans;
return 0;
}
标签:排序,int,51,交换,数组,火柴,P1966 From: https://www.cnblogs.com/genshin-player/p/18103666Written with StackEdit中文版.