题解 P1966 【火柴排队】
P1966 火柴排队 题解
这毕竟是个蓝题 于是时间过去了很久……
终于想出来了 本人不会树状数组 于是还是老老实实归并
不会的先看看思路，别急着看代码
其实这题本身并不难，考的知识点就是归并排序和逆序对； （附P1908 逆序对）
那么难点在哪呢？就在如何发现这题是个逆序对：
（附送题目链接：P1966 火柴排队）
于是我们先解读题目（以下是简化版）：
- 现有两列每列个数为n的火柴，且每列中火柴棒的高度均不相同，求得到Σ[(ai-bi)^2]的最小值的时候，最少需要交换火柴的次数，其中i表示a、b两列火柴棒中第i根火柴；
- 数据输入：
- 共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
- 第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
- 第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。
- 数据输出：一个整数，表示最少交换次数对 99,999,997 取模的结果。
数据范围：
-
对于 10%的数据， 1 ≤ n ≤ 10；
-
对于 30%的数据，1 ≤ n ≤ 100；
-
对于 60%的数据，1 ≤ n ≤ 1,000；
-
对于 100%的数据，1 ≤ n ≤ 100,000,0 ≤火柴高度≤ maxlongint；
至少读到这里我们可以知道，虽然火柴高度是唯一的，但我们不可能直接开一个 max long int 大小的数组！很明显，有一个考点：离散化！
好了回归题目，既然要求找到 min(Σ[(ai-bi)^2])，那么我们不妨变形一下：
Σ[(ai-bi)^2]=Σ(ai^2-2*ai*bi+bi^2)由此可见，若想使min(Σ[(ai-bi)^2])最小，而和式中ai^2+bi^2是个定值，那么，就只能在 2*aibi 这一项上下文章；
Σ(ai^2-2*ai*bi+bi^2)=Σ(ai^2+bi^2)-Σ(2*ai*bi)
Σ(2*ai*bi)=2*Σ(ai*bi)那么，我们要取 Σ(ai*bi)的最大值！这样，上述和式的值最小；
如何取到最大值？其实看过别人题解的也都清楚：
对于数列k1~kn,p1~pn，Σ(ki*pi)的最小值要求两个数列有序的分别从小到大（或从大到小）排列
即提出“假说”：对于有序数列k(1)~k(n),p(1)~p(n)，k(1)p(1)+k(2)p(2)+……+k(n)p(n)>=k(i)p(t)+k(u)p(y)+……+k(r)p(g)，意思就是说：顺序x顺序>=乱序x乱序；
如何证明？
看了Dalao们写的很多，我还是用数学知识证明一下好了：
公式证明： 顺序之乘>=乱序之乘
-
设有序数列k1~kn,p1~pn，取k1<k2、p1<p2
-
因此容易得到：k1p1+k2p2>k1p2+k2p1;
将上述不等式变形一下：
k2p2-k2p1>k1p2-k1p1 即k2(p2-p1)>k1(p2-p1) ∵k2>k1,p2>p1 ∴k2(p2-p1)>k1(p2-p1) 证毕； -
推广2中的结论到1中，乱序就是不断将顺序交换打乱的过程，最终结果符合2的结论，因此 顺序之乘>=乱序之乘，证毕。
我想我的证明还是比较易懂的吧QAQ
到此，题目解读完毕，证明完毕；
以下谈谈思路
- 离散化数据。既然数组没法开那么大，那么就对输入数据进行一下离散化。
实现如下：
struct fire{
int hi,bh;
}l1[1000005],l2[1000005]；
//……此处省略一大堆……
for(int i=1;i<=n;i++)
scanf("%d",&l1[i].hi),l1[i].bh=i;
for(int i=1;i<=n;i++)
scanf("%d",&l2[i].hi),l2[i].bh=i;
- 排列数。证明完成，那么我们要找的就是两个数列 l1, l2 中每一个数是否按我们所说的原则一一对应，比如说一个数列第1大的数对应另一个数列第1大的数，第2大的数对应另一个第2大的数，以此类推……
那么，不管三七二十一，先快排让两个序列有序一下吧（每个序列中火柴棒高度不同，不会导致编号混乱），反正有编号在那；然后我们来看一组数据（样例1）
A：2 3 1 4->1 2 3 4对应原编号为：3 1 2 4
B：3 2 1 4->1 2 3 4对应原编号为：3 2 1 4那么，A序列中输入的第一个数是第3小的，类推；
B序列中输入的第一个数是第3小的，符合，类推；
然我我们就发现了，A中第二个数与B中第二个数不一样（顺序不同），那么这就是一个逆序对，这个数不符合原则；不懂继续看看，等会就懂了；
-
找到不符合原则的数。
我们存一个数组c[i]; c[B[i]编号]=A[i]编号；为什么这么做？ 数据说话： A：2 3 1 4->1 2 3 4对应原编号为：3 1 2 4 B：3 2 1 4->1 2 3 4对应原编号为：3 2 1 4 c[B[1]编号]=c[3]=a[1]编号=3 c[B[2]编号]=c[2]=a[2]编号=1 c[B[3]编号]=c[1]=a[3]编号=2 c[B[4]编号]=c[4]=a[4]编号=4 于是c[1]=2 c[2]=1 c[3]=3 c[4]=4 逆序对数=1，交换一次，结束；神奇吗？不神奇，这就是排序；读到这里，读者应该对排序有了更深的理解；
为什么上述操作可以实现？因为产生了逆序；只要序列原来对应的数是符合要求的，他们编号相同，那么我们排完序两数的相对位置不发生改变，因此不会产生逆序；一旦A中编号与B中的不同，即大小顺序不同(顺序的整理快排都帮我们实现了)，那么这个数是不符合要求的，我们需要处理一下，剩下的在c数组中的数都是符合要求的(也就就是计入逆序对)。想到这里，程序就over了；不信的读者可以把第二个样例按我上面的分析写出来，自己也可以再写几组简单的样例，多过几遍流程；
上述操作实现如下(归并部分等会给)：
long long n,x[10000005],p[1000005],ans=0; bool cmp1(fire a,fire b) { return a.hi<b.hi; } //结构体在上面离散的时候就定义了，这里不写了； //……再省略…… sort(l1+1,l1+n+1,cmp1); sort(l2+1,l2+n+1,cmp1); //排序 for(int i=1;i<=n;i++) x[l2[i].bh]=l1[i].bh; //整理排序结果，我讲的用的c数组，我写的时候写的是x，没差； -
归并。这个我貌似不用说了，毕竟都做到蓝题了，没什么好讲的；但在归并中要求逆序对(其实冒泡也可以实现，但是太慢，会超时)，不懂请见P1908 逆序对 这个挺有用的。
至此，所有的分析与解就over了，与程序说再见
代码实现如下：
//认真看，杜绝抄袭
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod=99999997;
long long n,x[10000005],p[1000005],ans=0;
struct fire{
int hi,bh;
}l1[1000005],l2[1000005];
bool cmp1(fire a,fire b)
{
return a.hi<b.hi;
}
void msort(int s,int t)//归并排序;
{
if(s==t)return ;
int mid=(s+t)/2;
msort(s,mid);msort(mid+1,t);
int i=s,k=s,j=mid+1;
while(i<=mid && j<=t)
{
if(x[i]<=x[j])
{
p[k]=x[i];
++k;++i;
}
else
{
p[k]=x[j];
++k;++j;
ans=(ans+mid-i+1)%mod;
//此处找到逆序对，mid-i~mid中数全都与j构成逆序，还会少算一个，+1;
}
}
while(i<=mid)
{
p[k]=x[i];
++k;++i;
}
while(j<=t)
{
p[k]=x[j];
++k;++j;
}
for(int i=s;i<=t;i++)
{
x[i]=p[i];
}
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%d",&l1[i].hi),l1[i].bh=i;
for(int i=1;i<=n;i++)
scanf("%d",&l2[i].hi),l2[i].bh=i;
sort(l1+1,l1+n+1,cmp1);
sort(l2+1,l2+n+1,cmp1);
//排序;
for(int i=1;i<=n;i++)
x[l2[i].bh]=l1[i].bh;
msort(1,n);
//调用归并;
printf("%lld",ans);
return 0;//这个不会有人忘的吧？
}