华为OD机考双机位C卷 - 游戏分组（Java Python JS C/C++ GO ）-程序员充电站

题目描述

有n（n为2到24之间的偶数，包含2和24）位玩家参与一款在线对战游戏，游戏服务器会将玩家分为两组进行对战，每组人数为n/2。每位玩家都有一个战斗力，代表着这位玩家的厉害程度。为了对战尽可能精彩，分组时要做到两组的战斗力相差最小（每组的战斗力为组内玩家战斗力之和）。现在，给你n位玩家的战斗力，把他们分为战斗力相差最小的两组。请你输出这两组的战斗力差。

输入描述

n个整数，n为2到24之间的偶数（包含2和24），整数之间用空格分隔。每个整数均为0和500000000之间的数字（包含0和500000000），每个整数为一位玩家的战斗力值

输出描述

两组最小的战斗力差，整数

示例1

输入

1 2 3 4 5 6 7 8 9 10

输出

说明

示例2

输入

500 700 0 0

输出

说明

解题思路

Java

importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;publicclassMain{// 全局变量用于存储最小差值，初始化为最大长整型staticlongminDiff=Long.MAX_VALUE;staticlongtotalSum=0;staticintn;staticinttargetCount;// 每组需要的人数 (n/2)staticlong[]nums;// 存储玩家战斗力publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);// 读取输入// 题目描述输入为一行空格分隔的整数，我们将其读取到列表中List<Long>inputList=newArrayList<>();if(scanner.hasNextLine()){String[]parts=scanner.nextLine().trim().split("\\s+");for(Stringpart:parts){if(!part.isEmpty()){inputList.add(Long.parseLong(part));}}}// 初始化数据n=inputList.size();targetCount=n/2;nums=newlong[n];for(inti=0;i<n;i++){nums[i]=inputList.get(i);totalSum+=nums[i];}// 开始深度优先搜索// 参数：当前索引，已选人数，当前和dfs(0,0,0);// 输出结果System.out.println(minDiff);}/** * 深度优先搜索所有组合 * @param index 当前考虑的玩家索引 * @param count 当前已选入第一组的玩家数量 * @param currentSum 当前第一组的战斗力总和 */publicstaticvoiddfs(intindex,intcount,longcurrentSum){// 剪枝条件1：如果已经选够了 n/2 个人if(count==targetCount){// 计算两组的差值// 第一组和为 currentSum// 第二组和为 totalSum - currentSum// 差值 = |currentSum - (totalSum - currentSum)| = |2 * currentSum - totalSum|longdiff=Math.abs(2*currentSum-totalSum);// 更新最小差值if(diff<minDiff){minDiff=diff;}return;}// 剪枝条件2：如果剩余的可选人数不足以凑齐 targetCount，直接返回// (n - index) 是剩余可遍历的元素个数// (targetCount - count) 是还需要选的元素个数if((n-index)<(targetCount-count)){return;}// 策略1：选择当前玩家进入第一组dfs(index+1,count+1,currentSum+nums[index]);// 策略2：不选当前玩家进入第一组（即归入第二组）// 这里有个小优化：如果 diff 已经为 0，没必要继续搜了（虽然上面的逻辑没加，但在极值情况下会稍快）if(minDiff>0){dfs(index+1,count,currentSum);}}}

Python

importsys# 全局变量用于存储最小差值，初始化为最大长整型min_diff=sys.maxsize total_sum=0n=0target_count=0# 每组需要的人数 (n/2)nums=[]# 存储玩家战斗力defdfs(index,count,current_sum):globalmin_diff,total_sum,n,target_count,nums# 剪枝条件1：如果已经选够了 n/2 个人ifcount==target_count:# 计算两组的差值# 第一组和为 current_sum# 第二组和为 total_sum - current_sum# 差值 = |current_sum - (total_sum - current_sum)| = |2 * current_sum - total_sum|diff=abs(2*current_sum-total_sum)# 更新最小差值ifdiff<min_diff:min_diff=diffreturn# 剪枝条件2：如果剩余的可选人数不足以凑齐 target_count，直接返回# (n - index) 是剩余可遍历的元素个数# (target_count - count) 是还需要选的元素个数if(n-index)<(target_count-count):return# 策略1：选择当前玩家进入第一组dfs(index+1,count+1,current_sum+nums[index])# 策略2：不选当前玩家进入第一组（即归入第二组）# 这里有个小优化：如果 diff 已经为 0，没必要继续搜了ifmin_diff>0:dfs(index+1,count,current_sum)defmain():globaltotal_sum,n,target_count,nums,min_diff# 读取输入input_list=list(map(int,input().split()))# 初始化数据n=len(input_list)target_count=n//2nums=input_list total_sum=sum(nums)# 开始深度优先搜索dfs(0,0,0)# 输出结果print(min_diff)if__name__=="__main__":main()

JavaScript

constreadline=require('readline');// 全局变量用于存储最小差值，初始化为最大长整型letminDiff=Number.MAX_SAFE_INTEGER;lettotalSum=0;letn=0;lettargetCount=0;// 每组需要的人数 (n/2)letnums=[];// 存储玩家战斗力/** * 深度优先搜索所有组合 * @param {number} index 当前考虑的玩家索引 * @param {number} count 当前已选入第一组的玩家数量 * @param {number} currentSum 当前第一组的战斗力总和 */functiondfs(index,count,currentSum){// 剪枝条件1：如果已经选够了 n/2 个人if(count===targetCount){// 计算两组的差值// 第一组和为 currentSum// 第二组和为 totalSum - currentSum// 差值 = |currentSum - (totalSum - currentSum)| = |2 * currentSum - totalSum|constdiff=Math.abs(2*currentSum-totalSum);// 更新最小差值if(diff<minDiff){minDiff=diff;}return;}// 剪枝条件2：如果剩余的可选人数不足以凑齐 targetCount，直接返回// (n - index) 是剩余可遍历的元素个数// (targetCount - count) 是还需要选的元素个数if((n-index)<(targetCount-count)){return;}// 策略1：选择当前玩家进入第一组dfs(index+1,count+1,currentSum+nums[index]);// 策略2：不选当前玩家进入第一组（即归入第二组）// 这里有个小优化：如果 diff 已经为 0，没必要继续搜了if(minDiff>0){dfs(index+1,count,currentSum);}}constrl=readline.createInterface({input:process.stdin,output:process.stdout});rl.question('',(input)=>{// 读取输入nums=input.trim().split(/\s+/).map(Number);// 初始化数据n=nums.length;targetCount=Math.floor(n/2);totalSum=nums.reduce((a,b)=>a+b,0);// 开始深度优先搜索dfs(0,0,0);// 输出结果console.log(minDiff);rl.close();});

C++

#include<iostream>#include<vector>#include<string>#include<sstream>#include<climits>#include<cmath>// 全局变量用于存储最小差值，初始化为最大长整型longlongminDiff=LLONG_MAX;longlongtotalSum=0;intn;inttargetCount;// 每组需要的人数 (n/2)std::vector<longlong>nums;// 存储玩家战斗力/** * 深度优先搜索所有组合 * @param index 当前考虑的玩家索引 * @param count 当前已选入第一组的玩家数量 * @param currentSum 当前第一组的战斗力总和 */voiddfs(intindex,intcount,longlongcurrentSum){// 剪枝条件1：如果已经选够了 n/2 个人if(count==targetCount){// 计算两组的差值// 第一组和为 currentSum// 第二组和为 totalSum - currentSum// 差值 = |currentSum - (totalSum - currentSum)| = |2 * currentSum - totalSum|longlongdiff=std::abs(2*currentSum-totalSum);// 更新最小差值if(diff<minDiff){minDiff=diff;}return;}// 剪枝条件2：如果剩余的可选人数不足以凑齐 targetCount，直接返回// (n - index) 是剩余可遍历的元素个数// (targetCount - count) 是还需要选的元素个数if((n-index)<(targetCount-count)){return;}// 策略1：选择当前玩家进入第一组dfs(index+1,count+1,currentSum+nums[index]);// 策略2：不选当前玩家进入第一组（即归入第二组）// 这里有个小优化：如果 diff 已经为 0，没必要继续搜了if(minDiff>0){dfs(index+1,count,currentSum);}}intmain(){std::string line;std::getline(std::cin,line);std::istringstreamiss(line);longlongnum;// 读取输入while(iss>>num){nums.push_back(num);}// 初始化数据n=nums.size();targetCount=n/2;for(longlongnum:nums){totalSum+=num;}// 开始深度优先搜索dfs(0,0,0);// 输出结果std::cout<<minDiff<<std::endl;return0;}

Go

packagemainimport("fmt""math""strings""strconv")// 全局变量用于存储最小差值，初始化为最大长整型varminDiffint64=math.MaxInt64vartotalSumint64varnintvartargetCountint// 每组需要的人数 (n/2)varnums[]int64// 存储玩家战斗力/** * 深度优先搜索所有组合 * @param index 当前考虑的玩家索引 * @param count 当前已选入第一组的玩家数量 * @param currentSum 当前第一组的战斗力总和 */funcdfs(index,countint,currentSumint64){// 剪枝条件1：如果已经选够了 n/2 个人ifcount==targetCount{// 计算两组的差值// 第一组和为 currentSum// 第二组和为 totalSum - currentSum// 差值 = |currentSum - (totalSum - currentSum)| = |2 * currentSum - totalSum|diff:=int64(math.Abs(float64(2*currentSum-totalSum)))// 更新最小差值ifdiff<minDiff{minDiff=diff}return}// 剪枝条件2：如果剩余的可选人数不足以凑齐 targetCount，直接返回// (n - index) 是剩余可遍历的元素个数// (targetCount - count) 是还需要选的元素个数if(n-index)<(targetCount-count){return}// 策略1：选择当前玩家进入第一组dfs(index+1,count+1,currentSum+nums[index])// 策略2：不选当前玩家进入第一组（即归入第二组）// 这里有个小优化：如果 diff 已经为 0，没必要继续搜了ifminDiff>0{dfs(index+1,count,currentSum)}}funcmain(){varinputstringfmt.Scanln(&input)// 读取输入strNums:=strings.Fields(input)nums=make([]int64,len(strNums))fori,s:=rangestrNums{nums[i],_=strconv.ParseInt(s,10,64)totalSum+=nums[i]}// 初始化数据n=len(nums)targetCount=n/2// 开始深度优先搜索dfs(0,0,0)// 输出结果fmt.Println(minDiff)}

C语言

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<limits.h>#include<math.h>// 全局变量用于存储最小差值，初始化为最大长整型longlongminDiff=LLONG_MAX;longlongtotalSum=0;intn;inttargetCount;// 每组需要的人数 (n/2)longlong*nums;// 存储玩家战斗力/** * 深度优先搜索所有组合 * @param index 当前考虑的玩家索引 * @param count 当前已选入第一组的玩家数量 * @param currentSum 当前第一组的战斗力总和 */voiddfs(intindex,intcount,longlongcurrentSum){// 剪枝条件1：如果已经选够了 n/2 个人if(count==targetCount){// 计算两组的差值// 第一组和为 currentSum// 第二组和为 totalSum - currentSum// 差值 = |currentSum - (totalSum - currentSum)| = |2 * currentSum - totalSum|longlongdiff=llabs(2*currentSum-totalSum);// 更新最小差值if(diff<minDiff){minDiff=diff;}return;}// 剪枝条件2：如果剩余的可选人数不足以凑齐 targetCount，直接返回// (n - index) 是剩余可遍历的元素个数// (targetCount - count) 是还需要选的元素个数if((n-index)<(targetCount-count)){return;}// 策略1：选择当前玩家进入第一组dfs(index+1,count+1,currentSum+nums[index]);// 策略2：不选当前玩家进入第一组（即归入第二组）// 这里有个小优化：如果 diff 已经为 0，没必要继续搜了if(minDiff>0){dfs(index+1,count,currentSum);}}intmain(){charline[10000];fgets(line,sizeof(line),stdin);// 计算输入数字的个数n=0;char*token=strtok(line," \n");while(token!=NULL){n++;token=strtok(NULL," \n");}// 分配内存nums=(longlong*)malloc(n*sizeof(longlong));// 重新读取数字inti=0;token=strtok(line," \n");while(token