题解：最大配对绝对差之和

问题描述

给定两个长度为n的序列A和B，从A和B中各选n个元素进行一一配对，要求所有配对元素的绝对差之和最大。输出这个最大值。

输入输出格式

• 输入：
  • 第一行：一个整数n。
  • 第二行：n个整数，表示序列A。
  • 第三行：n个整数，表示序列B。
• 输出：
  • 一个整数，表示最大配对绝对差之和。

示例

输入：

4
2 5 6 3
1 4 6 7

输出：

14

解释： 配对方式为：3与6配对，2与7配对，5与4配对，6与1配对，绝对值之差和为 |3-6| + |2-7| + |5-4| + |6-1| = 3 + 5 + 1 + 5 = 14。

解题思路

贪心算法

这个问题可以通过贪心算法解决。贪心的核心思想是每次选择局部最优解，从而最终得到全局最优解。

具体步骤

1. 排序：

   • 将序列A按升序排序。
   • 将序列B按降序排序。

2. 配对：

   • 将排序后的A和B的对应位置元素进行配对，计算它们的绝对差之和。

为什么这样可行？

通过将A升序排序和B降序排序，可以确保A的最小值与B的最大值配对，A的次小值与B的次大值配对，以此类推。这样可以最大化每个配对的绝对差，从而最大化总和。

证明

我们需要证明：将A升序排序和B降序排序后，对应位置元素的配对能够使得绝对差之和最大。

假设存在另一种配对方式，其中存在两个元素对 ((a_i, b_j)) 和 ((a_k, b_l))，满足 (i < k) 且 (b_j < b_l)。根据贪心策略，应该将较大的 (a_k) 与较大的 (b_l) 配对，较小的 (a_i) 与较小的 (b_j) 配对。

假设我们交换这两个配对，即改为 ((a_i, b_l)) 和 ((a_k, b_j))。我们需要证明交换后的总和更大。

交换前的总和为： [ S = |a_i - b_j| + |a_k - b_l| ]

交换后的总和为： [ S' = |a_i - b_l| + |a_k - b_j| ]

我们需要证明 (S' \geq S)。

由于 (a_i < a_k) 且 (b_j < b_l)，我们可以展开绝对值： [ |a_i - b_j| + |a_k - b_l| \leq |a_i - b_l| + |a_k - b_j| ]

展开后： [ (a_i - b_j) + (b_l - a_k) \leq (b_l - a_i) + (a_k - b_j) ]

化简： [ a_i - b_j + b_l - a_k \leq b_l - a_i + a_k - b_j ]

进一步化简： [2a_i - 2a_k \leq 0]

即： [a_i \leq a_k]

这显然成立，因为 (i < k) 且A是升序排序的。因此，交换后的总和 (S') 一定大于等于原来的总和 (S)。

通过不断交换这样的元素对，最终可以得到贪心策略下的配对方式，即A升序、B降序后的对应位置配对，此时总和最大。

代码实现

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int a[10001], b[10001], n, ans;

// 升序排序
bool up(int a, int b) {
    return a < b;
}

// 降序排序
bool down(int a, int b) {
    return a > b;
}

int main() {
    // 输入n
    scanf("%d", &n);
    
    // 输入序列A
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    
    // 输入序列B
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }
    
    // 对A升序排序
    sort(a, a + n, up);
    
    // 对B降序排序
    sort(b, b + n, down);
    
    // 计算绝对差之和
    for (int i = 0; i < n; i++) {
        ans += abs(a[i] - b[i]);
    }
    
    // 输出结果
    printf("%d", ans);
    
    return 0;
}

总结

这道题的关键在于理解贪心算法的应用。通过将A升序排序和B降序排序，可以确保每个配对的绝对差最大，从而得到全局最优解。 PS: 时间复杂度为O(n log n)

C++ :

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int a[10010],b[10010];
int n;
void init();
void maopao(int a[]);
void work();
int main()
{
	init();
	work();
	return 0;
}
void init()
{
	//freopen("test0.in","r",stdin);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	for(int i=1;i<=n;++i)cin>>b[i];
}
void maopao(int a[])
{
	int temp,k;
	for(int i=1;i<=n;i++)
	{
		temp=a[i];
		k=i;
		for(int j=i;j<=n;j++)
		{
			if(temp>a[j])
			{
				temp=a[j];
				k=j;
			}
		}
		temp=a[i];
		a[i]=a[k];
		a[k]=temp;
	}
}
void work()
{
	maopao(a);
	maopao(b);
	int sum=0;
	int d;
	for(int i=1;i<=n;++i)
	{
		if(a[i]<b[n-i+1])d=b[n-i+1]-a[i];
		else d=a[i]-b[n-i+1];
		sum+=d;
	}
	cout<<sum<<endl;
}

Pascal :

type
  arr=array[1..10000]of longint;


var
 n,i,ans:longint;
 a,b:arr;


procedure readdata;
var
 i:longint;
begin
 readln(n);
 for i:=1 to n do
  read(a[i]);
 for i:=1 to n do
  read(b[i]);
end;


procedure qsort1(var a:arr;l,r: longint);
var
   i,j,x,y: longint;
begin
   i:=l;
   j:=r;
   x:=a[(l+r) shr 1];
   repeat
    while a[i]<x do
      inc(i);
    while x<a[j] do
      dec(j);
    if not(i>j) then
     begin
       y:=a[i];a[i]:=a[j];a[j]:=y;
       inc(i);dec(j);
     end;
  until i>j;
  if l<j then
    qsort1(a,l,j);
  if i<r then
    qsort1(a,i,r);
end;


procedure qsort2(var a:arr;l,r: longint);
var
   i,j,x,y: longint;
begin
   i:=l;
   j:=r;
   x:=a[(l+r) shr 1];
   repeat
    while a[i]>x do
      inc(i);
    while x>a[j] do
      dec(j);
    if not(i>j) then
     begin
       y:=a[i];a[i]:=a[j];a[j]:=y;
       inc(i);dec(j);
     end;
  until i>j;
  if l<j then
    qsort2(a,l,j);
  if i<r then
    qsort2(a,i,r);
end;


function abss(x:longint):longint;
begin
 if x<0 then exit(-x);
 exit(x);
end;


procedure greedy;
var
 i:longint;
begin
  qsort1(a,1,n);
  qsort2(b,1,n);
  for i:=1 to n do
   inc(ans,abss(a[i]-b[i]));
end;


begin
  readdata;
  greedy;
  writeln(ans);
end.