题目分析

给定 n 个队伍，每个队伍有一个实力值。我们希望将这些队伍进行配对，使得每一对的实力值差不超过给定的最大值 max_difference。我们的目标是计算出最大数量配对后的最小总实力差。如果无法进行任何有效的配对，则输出 -1。

解题思路

1. 排序：采用贪心的策略，首先将队伍的实力值进行排序，使得相邻队伍实力差值最小。

2. 动态规划：

   • 使用两个数组 dp 和 total_difference：
     • dp[i] 表示前 i 个队伍能形成的最大配对次数。
     • total_difference[i] 表示前 i 个队伍的最小总实力差。
   • 初始化 dp[0] 和 total_difference[0] 为 0，表示没有队伍时的状态。
   • 遍历队伍，利用动态规划的思想更新 dp 和 total_difference：
     • 对于每一对相邻的队伍，计算他们的实力差 current_difference。
     • 如果 current_difference 小于或等于 max_difference，则可以形成一对：
       • 更新 dp 和 total_difference，根据之前的状态选择最优解。
     • 如果不满足条件，则继续保持前面的状态。

3. 输出结果：根据 dp[num_teams] 判断是否有可配对的队伍，输出对应的最小总差距。

复杂度分析

• 时间复杂度：

  • 排序的时间复杂度为 (O(n \log n))。
  • 动态规划的遍历需要 (O(n))，因此总的时间复杂度为 (O(n \log n + n) = O(n \log n))。

• 空间复杂度：

  • 使用了 (O(n)) 的额外空间来存储 dp 和 total_difference 数组，因此空间复杂度为 (O(n))。

题目本质分析

这个问题可以看作是一个典型的动态规划问题，核心在于如何有效地管理状态转移。通过排序使得相邻元素的比较变得简单，能够快速地判断哪些队伍可以配对。同时，动态规划的方式帮助我们在每一步都选择最优解，最终得到全局最优解。

代码

Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int num_teams, max_difference;
    // 输入队伍数量和允许的最大实力差距
    cin >> num_teams >> max_difference;
    
    vector<int> team_strengths(num_teams);
    // 输入每个队伍的实力值
    for (int i = 0; i < num_teams; ++i) {
        cin >> team_strengths[i];
    }

    // 对实力值进行排序
    sort(team_strengths.begin(), team_strengths.end());
    
    // 初始化动态规划数组
    vector<int> dp(num_teams + 1, 0);  // 用于记录匹配的次数
    vector<int> total_difference(num_teams + 1, 0);  // 用于记录最小总差距

    // dp 数组初始值设为无匹配状态
    dp[0] = total_difference[0] = 0;
    dp[1] = total_difference[1] = 0;

    // 动态规划计算最小的总差距
    for (int i = 2; i <= num_teams; ++i) {
        int current_difference = team_strengths[i - 1] - team_strengths[i - 2];  // 计算当前队伍和前一个队伍的实力差
        
        if (current_difference <= max_difference) {  // 如果差距在允许范围内
            if (dp[i - 1] == dp[i - 2] + 1) {
                total_difference[i] = min(total_difference[i - 2] + current_difference, total_difference[i - 1]);
                dp[i] = dp[i - 1];
            } else {
                dp[i] = dp[i - 1] + 1;
                total_difference[i] = total_difference[i - 2] + current_difference;
            }
        } else {  // 如果差距不在允许范围内
            dp[i] = dp[i - 1];
            total_difference[i] = total_difference[i - 1];
        }
    }

    // 输出结果
    if (dp[num_teams] == 0) {  // 如果没有可匹配的对
        cout << "-1" << endl;
    } else {  // 输出最小的总差距
        cout << total_difference[num_teams] << endl;
    }

    return 0;
}

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 输入队伍数量和允许的最大实力差距
        int numTeams = scanner.nextInt();
        int maxDifference = scanner.nextInt();
        
        int[] teamStrengths = new int[numTeams];
        // 输入每个队伍的实力值
        for (int i = 0; i < numTeams; i++) {
            teamStrengths[i] = scanner.nextInt();
        }

        // 对实力值进行排序
        Arrays.sort(teamStrengths);
        
        // 初始化动态规划数组
        int[] dp = new int[numTeams + 1];  // 用于记录匹配的次数
        int[] totalDifference = new int[numTeams + 1];  // 用于记录最小总差距

        // dp 数组初始值设为无匹配状态
        dp[0] = totalDifference[0] = 0;
        dp[1] = totalDifference[1] = 0;

        // 动态规划计算最小的总差距
        for (int i = 2; i <= numTeams; i++) {
            int currentDifference = teamStrengths[i - 1] - teamStrengths[i - 2];  // 计算当前队伍和前一个队伍的实力差
            
            if (currentDifference <= maxDifference) {  // 如果差距在允许范围内
                if (dp[i - 1] == dp[i - 2] + 1) {
                    totalDifference[i] = Math.min(totalDifference[i - 2] + currentDifference, totalDifference[i - 1]);
                    dp[i] = dp[i - 1];
                } else {
                    dp[i] = dp[i - 1] + 1;
                    totalDifference[i] = totalDifference[i - 2] + currentDifference;
                }
            } else {  // 如果差距不在允许范围内
                dp[i] = dp[i - 1];
                totalDifference[i] = totalDifference[i - 1];
            }
        }

        // 输出结果
        if (dp[numTeams] == 0) {  // 如果没有可匹配的对
            System.out.println("-1");
        } else {  // 输出最小的总差距
            System.out.println(totalDifference[numTeams]);
        }

        scanner.close();
    }
}

Python

def main():
    # 输入队伍数量 num_teams 和允许的最大实力差距 max_difference
    num_teams, max_difference = map(int, input().split())
    
    # 输入每个队伍的实力值
    team_strengths = list(map(int, input().split()))
    
    # 对实力值进行排序
    team_strengths.sort()
    
    # 初始化动态规划数组
    dp = [0] * (num_teams + 1)  # 用于记录匹配的次数
    total_difference = [0] * (num_teams + 1)  # 用于记录最小总差距

    # dp 数组初始值设为无匹配状态
    dp[0] = total_difference[0] = 0
    dp[1] = total_difference[1] = 0

    # 动态规划计算最小的总差距
    for i in range(2, num_teams + 1):
        current_difference = team_strengths[i - 1] - team_strengths[i - 2]  # 计算当前队伍和前一个队伍的实力差
        
        if current_difference <= max_difference:  # 如果差距在允许范围内
            if dp[i - 1] == dp[i - 2] + 1:
                total_difference[i] = min(total_difference[i - 2] + current_difference, total_difference[i - 1])
                dp[i] = dp[i - 1]
            else:
                dp[i] = dp[i - 1] + 1
                total_difference[i] = total_difference[i - 2] + current_difference
        else:  # 如果差距不在允许范围内
            dp[i] = dp[i - 1]
            total_difference[i] = total_difference[i - 1]

    if dp[num_teams] == 0:  # 如果没有可匹配的对
        print("-1")
    else:  # 输出最小的总差距
        print(total_difference[num_teams])

if __name__ == "__main__":
    main()

题目内容

游戏里面，队伍通过匹配实力相近的对手进行对战。但是如果匹配的队伍实力相差太大，对于双方游戏体验都不会太好。

给定 $n$ 个队伍的实力值，对其进行两两实力匹配，两支队伍实例差距在允许的最大差距 $d$ 内，则可以匹配。

要求在匹配队伍最多的情况下匹配出的各组实力差距的总和最小。

输入描述

第一行，$n，d$ 。队伍个数 $n$ 。允许的最大实力差距 $d$ 。

• $2<=n <=50$
• $0<=d<=100$

第二行，$n$ 个队伍的实力值空格分割。

• $0<=$各队伍实力值$<=100$

输出描述

匹配后，各组对战的实力差值的总和。若没有队伍可以匹配，则输出 $-1$。

样例1

输入

6 30
81 87 47 59 81 18

输出

57

说明

$18$ 与 $47$ 配对，实力差距 $29$

$59$ 与 $81$ 配对，实力差距 $22$

$81$ 与 $87$ 配对，实力差距 $6$

总实力差距 $29+22+6=57$

样例2

输入

6 20
81 87 47 59 81 18

输出

12

说明

最多能匹配成功4支队伍。

$47$ 与 $59$ 配对，实力差距 $12$ ，

$81$ 与 $81$ 配对，实力差距 $0$ 。

总实力差距 $12+0=12$

样例3

输入

4 10
40 51 62 73

输出

-1

说明

实力差距都在 $10$ 以上，

没有队伍可以匹配成功。