[NOIP2013] 火柴排队 题解
Asika391
·
·
题解
这题目在处理序列上还是很有价值的。
题目要求我们最小化\sum(a_{i}-b_{i})^2，首先第一个给我们的启示是：遇到这种相互约束的式子，我们可以考虑将其拆开，变成容易维护的式子。
因为\sum(a_i-b_i)^2=\sum (a_i^2+b_i^2)-2\times\sum a_i\times b_i。前者显然是一个定值，我们要求的就是\sum a_i\times b_i的最大值。高中数学选修4-5里面有一个不等式叫排序不等式（所以数学是很重要的！）：
若a_1\leq a_2\leq a_3\leq \cdots\leq a_n与b_1\leq b_2\leq b_3\leq \cdots\leq b_n那么有a_1b_n+a_2b_{n-1}+\cdots +a_nb_1\leq a_{i1}b_{j1}+a_{i2}b_{j2}+\cdots +a_{in}b_{jn}\leq a_1b_1+a_2b_2+\cdots +a_nb_n即反序和\leq乱序和\leq同序和。
有了这个结论，我们只需要使使两列火柴的高度一一对应就好了（就是使最大与最大排在一起，以此列推）。
那么第二个思考来了：在只涉及大小关系中，我们可以将数据离散化。以下给出一个离散化的代码：
bool cmp(int i,int j){return A[i]<A[j];}
for(int i=1;i<=n;++i) scanf("%d",&A[i]),a[i]=i;
sort(a+1,a+1+n,cmp);
其中A数组是读入的火柴高度。我们发现经过这样离散化后，a[i]表示的是i这个数字在A中的位置（A数组中排名为i的数）(可以手玩一下)。
我们对A,B数组都经过这样离散化后，设离散化后的数组为a,b，新建一个数组l并令l[a[i]]=b[i]这样操作后我们会发现l[i]表示的是A中i这个位置的数在B中的位置。
举个例子吧，若初始的火柴高度是:
$B=${$1,7,2,4$}
我们先将其离散化一下便于理解，实际操作中并没有这一步,得到$A=${$1,3,4,2$},$B=${$1,4,2,3$}，那么离散化后的数组$a=${$1,4,2,3$}与$b=${$1,3,4,2$}那么得到的$l=${$1,4,2,3$}这正好对应了将$B$中$1$作为$1$，$4$作为$2$，$2$作为$3$，$3$作为$4$(按$1,2,3,4$升序)将$A$替换后的结果这时候，我们只要将$l$交换到$1,2,3,4$的状态就满足了。因为题目告诉我们每列火柴高度不重复并且每次交换只交换相邻两根火柴，这时候就是直接用树状数组计算$l$数组的逆序对就可以了。
附上代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005,mod=99999997;
int A[N],B[N],a[N],b[N],l[N],c[5*N];
ll ans;
int n;
void add(int x,int y){
for(;x<=n;x+=x&-x) c[x]+=y;
}
int ask(int x){
ll ans=0;
for(;x;x-=x&-x) ans+=c[x];
return ans;
}
bool cmp1(int i,int j){
return A[i]<A[j];
}
bool cmp2(int i,int j){
return B[i]<B[j];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&A[i]),a[i]=i;
for(int i=1;i<=n;++i) scanf("%d",&B[i]),b[i]=i;
sort(a+1,a+1+n),sort(b+1,b+1+n);//离散化
sort(a+1,a+1+n,cmp1),sort(b+1,b+1+n,cmp2);
for(int i=1;i<=n;++i) l[a[i]]=b[i];
for(int i=n;i;i--){//树状数组求逆序对
ans=(ans+ask(l[i]-1))%mod;
add(l[i],1);
}
printf("%lld",ans%mod);
return 0;
}
```