自动搬运

查看原文

来自洛谷，原作者为

	xiejinhao 人间总有一两风，填我十万八千梦

搬运于2025-08-24 21:32:24，当前版本为作者最后更新于2019-04-19 00:53:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P1966 火柴排队 题解

这毕竟是个蓝题 于是时间过去了很久……

终于想出来了 本人不会树状数组 于是还是老老实实归并

不会的先看看思路，别急着看代码

其实这题本身并不难，考的知识点就是归并排序和逆序对； （附P1908 逆序对）

那么难点在哪呢？就在如何发现这题是个逆序对：

（附送题目链接：P1966 火柴排队）

于是我们先解读题目（以下是简化版）：

• 现有两列每列个数为n的火柴，且每列中火柴棒的高度均不相同，求得到Σ[(ai-bi)^2]的最小值的时候，最少需要交换火柴的次数，其中i表示a、b两列火柴棒中第i根火柴；
• 数据输入：

1. 共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
2. 第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
3. 第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

• 数据输出：一个整数，表示最少交换次数对 99,999,997 取模的结果。

数据范围：

1. 对于 10%的数据， 1 ≤ n ≤ 10；

2. 对于 30%的数据，1 ≤ n ≤ 100；

3. 对于 60%的数据，1 ≤ n ≤ 1,000；

4. 对于 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们写的很多，我还是用数学知识证明一下好了：

公式证明： 顺序之乘>=乱序之乘

1. 设有序数列k1~kn,p1~pn，取k1<k2、p1<p2

2. 因此容易得到：k1p1+k2p2>k1p2+k2p1;

   将上述不等式变形一下：

     k2p2-k2p1>k1p2-k1p1 即k2(p2-p1)>k1(p2-p1)
    ∵k2>k1,p2>p1 ∴k2(p2-p1)>k1(p2-p1)
    证毕；
   

3. 推广2中的结论到1中，乱序就是不断将顺序交换打乱的过程，最终结果符合2的结论，因此 顺序之乘>=乱序之乘，证毕。

我想我的证明还是比较易懂的吧QAQ

到此，题目解读完毕，证明完毕；

以下谈谈思路

1. 离散化数据。既然数组没法开那么大，那么就对输入数据进行一下离散化。

实现如下：

  	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;

2. 排列数。证明完成，那么我们要找的就是两个数列 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中第二个数不一样（顺序不同），那么这就是一个逆序对，这个数不符合原则；不懂继续看看，等会就懂了；

3. 找到不符合原则的数。

    我们存一个数组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，没差；

3. 归并。这个我貌似不用说了，毕竟都做到蓝题了，没什么好讲的；但在归并中要求逆序对(其实冒泡也可以实现，但是太慢，会超时)，不懂请见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;//这个不会有人忘的吧？ 
}

---

这题还是基础吧，就是比较灵活

然后，Dalao看完点个赞好不好