最大匹配的数学证明

当数组a是递增排序，而数组b是递减排序时；或者数组a是递减排序，而数组b是递增排序时，结果最大。首先，这两种情况呈现一个对称关系，不妨证明前者——当数组a是递增排序，而数组b是递减排序时，结果最大。

1. 证明以下不等式：a1≥a2，b1≤b2时，有|a1-b1|+|a2-b2|≥|a1-b2|+|a2-b1|

       先讨论数字相等的情况，四个数字至少有两个相等，分成以下几类：a1=a2，b1=b2；a1=a2，b1≠b2；a1≠a2，b1=b2；a1=b1=a2=b2等等，这些都非常容易证明

       再证明四个数字互不相等的情况，一共有以下几类：b1<b2<a2<a1；b1<a2<b2<a1；b1<a2<a1<b2；a2<b1<b2<a1；a2<b1<a1<b2；a2<a1<b1<b2，采用作图法进行证明，在数轴上描出这些点即可判断

  2.设数组a是递增排序，则数组b是递减排序时，结果最大

    若数组b是常数数组，无论什么排序，结果都一样

    若数组b不是常数数组，假设数组b不在递减排序下取得最大结果，由于数组b不是递减排序，因此会出现数组b的某个数字b1排在某个数字b2的前面，而且b1≥b2，交换这两个数字得到数组b的一个新排序，由结论1，会使结果值增大，矛盾。因此，

参考代码:

#include<algorithm>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	int *a=(int *)malloc(n*sizeof(int)),*b=(int *)malloc(n*sizeof(int));
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<n;i++)
		scanf("%d",&b[i]);
	sort(a,a+n);
	sort(b,b+n);
	int num=0;
	for(int i=0;i<n;i++)
		num=num+abs(a[i]-b[n-1-i]);
	printf("%d",num);
}