云南省城乡建设培训中心网站,天津seo技术教程,莘县做网站推广,佳城建站 网站1、题目描述
【篮球比赛】 一个有N个选手参加比赛#xff0c;选手编号为1~N#xff08;3N100#xff09;#xff0c;有M#xff08;3M10#xff09;个评委对选手进行打分。 打分规则为每个评委对选手打分#xff0c;最高分10分#xff0c;最低分1分。…1、题目描述
【篮球比赛】 一个有N个选手参加比赛选手编号为1~N3N100有M3M10个评委对选手进行打分。 打分规则为每个评委对选手打分最高分10分最低分1分。 请计算得分最多的3位选手的编号。 如果得分相同则得分高分值最多的选手排名靠前 (10分数量相同则比较9分的数量以此类推用例中不会出现多个选手得分完全相同的情况)。 【输入描述】 10个篮球队员的战斗力(整数,范围[1, 10000])战斗力之间用空格分隔如:10987654321 不需要考虑异常输入的场景。 【输出描述】 最小的战斗力差值如:1 【示例1】 【输入】 10 9 8 7 6 5 4 3 2 1 【输出】 说明: . 1 2 5 9 10分为一队3 4 6 7 8分为一队两队战斗之差最小输出差值1。 备注:球员分队方案不唯一 但最小战斗力差值固定是1。
2、解题思路
该题类似于将10个数分成两组使得两组的数和之差最小。最小战斗力从差值0开始不满足依次增加差值为0即将10个战斗力之和平分给两组若无法平分则不满足差值增加。若满足则利用回溯算法统计满足选出5个数且之后恰好为平均值的数。
3、参考代码
import java.util.Arrays;
import java.util.Scanner;/*** Author * Date 2023/6/11 15:15*/
public class 篮球比赛 {public static void main(String[] args) {Scanner in new Scanner(System.in);while (in.hasNext()) {int[] array Arrays.stream(in.nextLine().split( )).mapToInt(Integer::parseInt).toArray();int totalSum 0;for (int arr : array) {totalSum arr;}// 从0开始找最小差值战斗力for (int i 0; i totalSum; i) {int target (totalSum - i);if (target % 2 0) { // 总和减去差值可以被平分为两组if (dfs(array, 0, target / 2, new boolean[10])) {System.out.println(i); // 能匹配则输出break;}}}}}// 回溯 遍历搜索分配球员public static boolean dfs(int[] array, int startIndex, int sum, boolean[] used) {if (startIndex 5 || sum 0) {return false;}if (startIndex 5 sum 0) {return true;}for (int i 0; i array.length; i) {if (used[i]) {continue;}used[i] true;if (dfs(array, startIndex 1, sum - array[i], used)) {return true;}used[i] false; // 回溯 不选}return false;}
}4、相似题目
1代码随想录回溯算法组合题型
