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

问题描述

给定两个长度为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)