华为OD机考算法题：篮球比赛

目录

题目部分

解读与分析

代码实现

题目部分

解读与分析

题目解读：

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 一定小于 sum
 		
		List<Integer> numList = new ArrayList<Integer>( 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, List<Integer> numbers )
	{			
		if( currentCnt + numbers.size() < 5 )
		{
			return SUM;
		}
		
		List<Integer> tmpRemovedNumber = new ArrayList<Integer>(); 
		
		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 一定小于 sum
 
    minDiff = 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;
}

(完)