著名的网站建设平台,有趣网站之家,网站开发与管理心得体会,网页游戏推广平台目录
题目部分
解读与分析
代码实现 题目部分
题目篮球比赛难度难题目说明篮球(5V5)比赛中#xff0c;每个球员拥有一个战斗力#xff0c;每个队伍的所有球员战斗力之和为该队伍的总体战斗力。现有 10 个球员准备分为两队进行训练赛#xff0c;教练希望 2 个队伍的战斗力…目录
题目部分
解读与分析
代码实现 题目部分
题目篮球比赛难度难题目说明篮球(5V5)比赛中每个球员拥有一个战斗力每个队伍的所有球员战斗力之和为该队伍的总体战斗力。现有 10 个球员准备分为两队进行训练赛教练希望 2 个队伍的战斗力差值能够尽可能的小以达到最佳训练效果。给出 10 个球员的战斗力如果你是教练你该如何分队才能达到最佳训练效果?请说出该分队方案下的最小战斗力差值。输入描述10 个篮球队员的战斗力(整数范围[110000])战斗力之间用空格分隔如10 9 8 7 6 5 4 3 2 1。 不需要考虑异常输入的场景。输出描述输出描述最小的战斗力差值如1。补充说明无------------------------------------------------------示例示例1输入10 9 8 7 6 5 4 3 2 1输出1说明1、2、5、9、10 分为一队3、4、6、7、8分为一队两队战斗力之差最小输出差值1。备注球员分队方案不唯一但最小战斗力差值固定是1。 解读与分析
题目解读
10 个数字分成两组每组 5 个数字使两组数字之和的差值最小。请输出最小差值。
分析与思路
本题与《华为OD机考算法题MVP争夺战》类似都是把数字分组要求分组后的数字达到某种要求。不同的是在《MVP争夺战》中每组的数字个数是不定的而在本题中每组数字的个数是固定的都是 5。相对而言本题的思路和实现更简单。
从 10 个数中穷尽所有的情况每种情况计算一下两队的差值找出差值最小的那个。
假设这两组分别为 A 组和 B 组这 10 个数字分别为 、……。 我们穷尽的顺序是先把 放到 A 组然后基于剩下的 9 个数字采用相同的方法穷尽 9 个数字取 4 个的所有可能情况。这样从 10 个数字中取 5 个的情况就降维成了 9 个数字取 4 个同样的方法最后可以降为成 6 个数字里取 1 个。 以上是 放到 A 组的情况接下来就是 放到 A 组然后从 到 这 8 个数字中穷尽 8 个数字 取 4 个数字的所有可能情况。
每遍历一种情况计算两组的数字之差设为 diff时如果 diff 比之前遍历时计算的最小差设为minDiff更小那么更新 minDiff 的值。遍历完所有情况后最终求得的 minDiff 值即为题目所要求的输出。这种算法遍历的次数为 。
在以上的遍历算法中存在重复计算的情况。题目只关心两组的差值所以在任意一种组合把 A 组的数字和 B 组的数字交换可以看做是同一种情况。如 、、、、 放到 A 组 与 、、、、 放到 A 组其实是等同的。为了减少重复我们可以假设 A 组的数字之和小于或等于 B 组的数字之和即 A 组数字之和小于或等于所有数字之和设为 sum的一半。那么在穷举所有情况时发现 A 组数字之和已经超过 (sum/2)那么就可以忽略这种组合了。这样可以减少一半遍历遍历次数变为 。
既然需要保证A组数字之和小于或等于 (sum/2)我们可以先对数字进行从小到大排序进一步减少遍历次数。
综上此算法的遍历次数不超过 。下面我们计算一下最大遍历次数。
由组合计算公式 可以得出 126最多不超过 126 次。 代码实现
Java代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;/*** 篮球比赛* since 2023.09.15* version 0.1* author Frank**/
public class BasketballGame {public static void main(String[] args) {Scanner sc new Scanner(System.in);while (sc.hasNext()) {String input sc.nextLine();String[] strNumbers input.split( );// 此处 count numbers.count可以完全不用考虑 count.processBasketballGame( strNumbers );}}private static void processBasketballGame( String strNumbers[] ){Integer[] numbers new Integer[strNumbers.length];int sum 0;for( int i 0; i numbers.length; i ){numbers[i] Integer.parseInt( strNumbers[i] );sum numbers[i];}Arrays.sort( numbers );int minDiff sum; // minDiff 一定小于 sumListInteger numList new ArrayListInteger( Arrays.asList( numbers ) );minDiff getMinDiff( sum, minDiff, 0, 0, numList );System.out.println( minDiff );}private static int getMinDiff( int SUM, int minDiff, int currentSum, int currentCnt, ListInteger numbers ){ if( currentCnt numbers.size() 5 ){return SUM;}ListInteger tmpRemovedNumber new ArrayListInteger(); for( int i 0; i numbers.size(); i ){int tmpMinDiff SUM;int tmpNumber numbers.get( i );int tmpCurrentSum currentSum tmpNumber;int tmpCurrentCnt currentCnt 1;if( tmpCurrentSum * 2 SUM ){break; // 可以break因为后面的数字更大。}if( tmpCurrentCnt 5 ){tmpMinDiff SUM - tmpCurrentSum * 2;if( tmpMinDiff minDiff ){minDiff tmpMinDiff;continue;}}tmpRemovedNumber.add( tmpNumber );numbers.remove( i );tmpMinDiff getMinDiff( SUM, minDiff, tmpCurrentSum, tmpCurrentCnt, numbers );if( tmpMinDiff minDiff ){minDiff tmpMinDiff;}
// numbers.add( i, tmpNumber ); // 不必加回去可以减少一半的穷举数} for( int i 0; i tmpRemovedNumber.size(); i ){numbers.add( i, tmpRemovedNumber.get( i ) );}return minDiff;}} JavaScript代码
const rl require(readline).createInterface({ input: process.stdin });
var iter rl[Symbol.asyncIterator]();
const readline async () (await iter.next()).value;
void async function() {while (line await readline()) {// count 可以忽略var strNumbers line.split( );processBasketballGame(strNumbers);}
}();function processBasketballGame(strNumbers) {var numbers new Array();var sum 0;for (var i 0; i strNumbers.length; i) {numbers[i] parseInt(strNumbers[i]);sum numbers[i];}numbers.sort();var minDiff sum; // minDiff 一定小于 summinDiff getMinDiff(sum, minDiff, 0, 0, numbers);console.log(minDiff);
}function getMinDiff(SUM, minDiff, currentSum, currentCnt, numbers) {if (currentCnt numbers.length 5) {return SUM;}var tmpRemovedNumber new Array();for (var i 0; i numbers.length; i) {var tmpMinDiff SUM;var tmpNumber numbers[i];var tmpCurrentSum currentSum tmpNumber;var tmpCurrentCnt currentCnt 1;if (tmpCurrentSum * 2 SUM) {break; // 可以break因为后面的数字更大。}if (tmpCurrentCnt 5) {tmpMinDiff SUM - tmpCurrentSum * 2;if (tmpMinDiff minDiff) {minDiff tmpMinDiff;continue;}}tmpRemovedNumber.push(tmpNumber);numbers.splice(i, 1);tmpMinDiff getMinDiff(SUM, minDiff, tmpCurrentSum, tmpCurrentCnt, numbers);if (tmpMinDiff minDiff) {minDiff tmpMinDiff;}}for (var i 0; i tmpRemovedNumber.length; i) {numbers.splice(i, 0, tmpRemovedNumber[i]);}return minDiff;
} (完)
