最佳对手实力差距最小总和

题目描述

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

给定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

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

//最佳对手实力差距最小总和

/**
  动态规划五部曲:
 1.dp[i]数组含义:代表 i 个队伍能匹配的队伍数量
 2.递推公式:if (dp[i - 1] < dp[i - 2] + 1) {dp[i] = dp[i - 2] + 1;  }
  表示如果当前队伍i能和i-1配对, 并且 配对后的总对数dp[i-2]+1 比不配对i的总对数dp[i - 1]更多,则匹配i ;反之不匹配队伍i,dp[i]=dp[i-1]
 3.初始化dp数组: 队伍小于等于2的情况
 4.遍历顺序,从左往右
 5.打印dp数组
 */

public class Solution200_20 {
    // 通用 split 函数
    public static List<String> split(String str, String delimiter) {
        return Arrays.asList(str.split(delimiter));
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), d = scanner.nextInt();
        scanner.nextLine(); // 处理换行符

        String s = scanner.nextLine();
        List<String> ansStr = split(s, " ");
        int[] ans = new int[n];

        for (int i = 0; i < n; i++) {
            ans[i] = Integer.parseInt(ansStr.get(i));
        }

        // 排序
        Arrays.sort(ans);

        // 1.dp数组含义:dp[i] 代表 i 个队伍能匹配的队伍数量
        int[] dp = new int[n];

        // minSum[i] i 个队伍匹配之后差值的和
        int[] minSum = new int[n];

        //2.初始化dp数组, 当只有两只队伍,并且能够组成1队,则dp[1]=1。
        if (ans[1]-ans[0]<=d){
            dp[1]=1;
            minSum[1]=ans[1]-ans[0];
        }

        for (int i = 2; i <n; i++) {
            //如果当前队伍和上一个队伍能够匹配
            boolean canMatch = ans[i] - ans[i - 1] <= d;

            if (canMatch) {
                // 优先选择匹配数量多的,匹配数量相等的选择差异值和小的

                //dp[i-1] 表示 i-1个队伍最大匹配对数 ;dp[i-2]表示 i-2队伍最大匹配对数 , +1表示 当前 队伍i要和i-1组成一队
                //如果和当前i队伍匹配能获得更多队伍数量,则队伍i加入
                if (dp[i - 1] < dp[i - 2] + 1) {
                    dp[i] = dp[i - 2] + 1;
                    minSum[i] = minSum[i - 2] + ans[i] - ans[i - 1];
                }
                //如果当前队伍i和i-1配对后的总对数 不变,则取总实力差值最小的情况:
                // 1. i和i-1配对:minSum[i - 2] + ans[i] - ans[i - 1];
                // 2.i不进行配对(直接取i-1的总实力差值)
                //注意:i和i-1配对后,只会出现 配对对数变多或者不变 ,不可能出现变少的情况!!
                else {
                    dp[i] = dp[i - 1];
                    minSum[i] = Math.min(minSum[i - 1], minSum[i - 2] + ans[i] - ans[i - 1]);
                }
            //如果当前队伍实力无法匹配上一个队伍,则直接复制i-1的值
            } else {
                dp[i] = dp[i - 1];
                minSum[i] = minSum[i - 1];
            }
        }

        System.out.println(dp[n-1] == 0 ? -1 : minSum[n-1]);
    }
}


全部评论

相关推荐

鼠鼠实习的地方是一个小小厂,让我去的时候offer都没发,面试也是线下面的。实习第一天上午拉代码本地跑完之后,下午就让我改sql。第二天跟鼠鼠说了一个需求,需求也没有说清楚,接口文档之类的都没有,就口头说了一声。第三天写昨天的功能。第四天开发一个新接口,要求也没说,我完全都在自己写,提交之后改了两回sql,然后就寄了😅。下班回家的时候,跟我一起实习的那个大哥知道之后跟我说,其实导师第四天下午就在看别人的简历了😓,下午下班的时候,把我叫到会议室,大概意思就是说我态度不端正,然后后面还扯了什么加班之类的,连改的机会都不给我直接就让我不用来了,估计是找到比我好的了。其实鼠鼠也挺委屈的,因为是第一次实习,想快点做出成绩,回头想想,确实太急功近利了,着急做出成绩导致代码有bug,还有就是导师需求都说不清,我只能一直问他(鼠鼠也只是想把功能做好),可能让他有点烦了吧,没想到第一次实习会是这样,真应了鼠鼠那句话,自诩心比天高,可叹命比纸薄。鼠鼠我这一路也挺曲折的,第一次面试就遇到了kpi(演都不演的那种),第一次实习就出现了这种状况。现在已经在回家的路上,准备回去沉淀一个暑假,到时候直接投中大厂了,现在也想开了,鼠鼠学历还行(末2软件工程),没必要为了实习而实习。鼠鼠的大致情况是javase,ssm,juc,jvm,mysql,redis,springcloud,springai,rabbitmq。八股文把小林coding背了几遍(上面那些技术栈相关的),算法大概刷了200道,感觉还得沉淀一下,牛客的友友们,有什么建议吗?希望各位义父能给鼠鼠点建议。
SoudX:找个好点的厂,我旁边的正职就是你学长,无实习经历校招进来的,你这才27届,多投一投
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务