2023华为OD机试真题-最佳对手(JAVA、Python、C++)

题目描述： 游戏里面，队伍通过匹配实力相近的对手进行对战。 但是如果匹配的队伍实例相差太大，对于双方游戏体验都不会太好。 给定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以上，没有队伍可以匹配成功。

import java.util.*;
 
public class Main{
    
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int limit = input.nextInt();
        int[] scores = new int[n];
        for(int i=0; i<n; i++){
            scores[i] = input.nextInt();
        }
        
        Arrays.sort(scores);
        int ans = 0;
        boolean flag =false;
        int[] dp = new int[n];
        dp[0] = 0;
        if(scores[1]-scores[0]<= limit){
            dp[1] = scores[1]-scores[0];
            flag = true;
        }else{
            dp[1] = 0;
        }
        for(int i=2; i<n; i++){
            if(scores[i] - scores[i-1] <= limit){
                flag = true;
                dp[i] = dp[i-2]+scores[i]-scores[i-1];
            }
            else
                dp[i] = dp[i-1];
        }
        if(flag){
            System.out.print(dp[n-1]);
        }else{
            System.out.print(-1);        
        }
    }
    
}