题目：MVP争夺战
知识点DFS搜索
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
在星球争霸篮球赛对抗赛中，强大的宇宙战队，希望每个人都能拿到MVP。
MVP的条件是，单场最高分得分获得者，可以并列，所以宇宙战队决定在比赛中，尽可能让更多的队员上场，且让所有有得分的队员得分都相同。
然而比赛过程中的每一分钟的得分都只能由某一个人包揽。
输入描述：
输入第一行为一个数字t，表示有得分的分钟数（ 1 <= t <= 50），第二行为t个数字，代表每一分钟的得分p（1 <= p <= 50）
输出描述：
输出有得分的队员都是MVP时最少的MVP得分。
示例1
输入：
9
5 2 1 5 2 1 5 2 1
输出：
6
说明：
样例解释：一共4人得分，分别都为6分
5 + 1
5 + 1
5 + 1
2 + 2 + 2
解题思路：
此题应该是正确率最低的题目了，只有0.71%；
首先对得分数组进行排序，确定平均得分的最小值和最大值。
最小值：得分数组的最大值（因为每一分钟的得分都只能由某一个人包揽）
最大值：得分总数/2（最低两个人平分）
从最小值遍历到最大值，需要注意的是，只有总得分整除平均分时才有必要去判断。判断的时候需要从最大值开始遍历（也就是得分数组尾部）
如示例1：
9
5 2 1 5 2 1 5 2 1
对数组进行排序 1 1 1 2 2 2 5 5 5 总分24
最小平均分：5，最大平均分：24/2=12
当n=5：（从数组尾部开始）
i=8，ints[8]=5，5-5=0，则满足平均分，使用过的得分置零ints[8]=0
i=7，ints[7]=5，5-5=0，则满足平均分，使用过的得分置零ints[7]=0
i=6，ints[6]=5，5-5=0，则满足平均分，使用过的得分置零ints[6]=0
i=5，ints[5]=2，5-2=3；
i=4，ints[4]=2，3-2=1；
…
i=2，ints[2]=1，1-1=0，满足平均分，使用过的得分置零ints[5]= ints[4]= ints[2]=0；
i=4，ints[4]=0，跳过。
i=3，ints[3]=2，5-2=3；
i=2，ints[2]=0，跳过；
i=1，ints[1]=1，3-1=2；i=0，ints[0]=1，2-1=1，不满足平均分。
最终数组剩下的总分4！=0，说明不能对平均分=5进行平分。
当n=6：（从数组尾部开始）
i=8，ints[8]=5，n=6-5=1；
i=7，ints[7]=5，1-5=-4<0，还原到n=1；
i=6，ints[6]=5，1-5=-4<0，还原到n=1；
i=5，ints[5]=2，1-2=-1<0，还原到n=1；
…
i=2，ints[2]=1，1-1=0，,满足平均分，使用过的得分置零ints[8]= ints[2]=0;
i=7，ints[7]=5，n=6-5=1；
i=6，ints[6]=5，1-5=-4<0，还原到n=1；
i=5，ints[5]=2，1-2=-1<0，还原到n=1；
…
i=2，ints[2]=0,跳过；
i=1，ints[1]=1，1-1=0，满足平均分，使用过的得分置零ints[7]= ints[1]=0;
i=6，ints[6]=5，n=6-5=1；
i=5，ints[5]=2，1-2=-1<0，还原到n=1；
i=4，ints[4]=2，1-2=-1<0，还原到n=1；
…
i=2，ints[2]=0,跳过；
i=1，ints[1]=0，跳过；
i=0，ints[0]=1，1-1=0，满足平均分，使用过的得分置零ints[6]= ints[0]=0;
i=5，ints[5]=2，n=6-2=4；
i=4，ints[4]=2，4-2=2；
i=3，ints[3]=2，2-2=0，满足平均分，使用过的得分置零ints[5]= ints[4]= ints[3]=0;
最终数组剩下的总分0==0，说明能对平均分=6进行平分。
以此类推。。。
最终最少的MVP得分为6
以下测试用例是真实机试中的：
20 1 2 3 4 5 6 7 8 9 21 23 24 25 26 28 27 26 29
3 1 4 10
4 1 2 3 4
1 1
9 5 2 1 5 2 1 5 2 1
40 6 6 6 6 6 6 6 6 6 6 9 9 9 9 9 9 9 9 9 9 40 40 40 40 40 40 40 40 40 40 1 2 3 9 8 7 4 5 6 10
11 8 50 49 1 1 13 15 17 49 50 50
20 1 2 3 4 5 6 7 8 9 21 23 24 25 26 28 27 26 29
3 1 4 10
4 1 2 3 4
1 1
9 5 2 1 5 2 1 5 2 1
40 6 6 6 6 6 6 6 6 6 6 9 9 9 9 9 9 9 9 9 9 40 40 40 40 40 40 40 40 40 40 1 2 3 9 8 7 4 5 6 10
11 8 50 49 1 1 13 15 17 49 50 50
代码实现一：
package com.codernav.demo.hwod.exam;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
/**
* @title MVP争夺战
* @Description 在星球争霸篮球赛对抗赛中，强大的宇宙战队，希望每个人都能拿到MVP。
* MVP的条件是，单场最高分得分获得者，可以并列，所以宇宙战队决定在比赛中，尽可能让更多的队员上场，且让所有有得分的队员得分都相同。
* 然而比赛过程中的每一分钟的得分都只能由某一个人包揽
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/14
*/
public class Main {
public static int score = 0; //MVP得分
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
sc.nextLine();
String[] p = sc.nextLine().split(" ");
int[] ints = new int[t];
for (int i = 0; i < p.length; i++) {
ints[i] = Integer.parseInt(p[i]);
}
int count = Arrays.stream(ints).sum();
Arrays.sort(ints); //对数组进行排序，
int min = ints[t - 1]; //求出数组中最大值，为MVP最低得分
int res = 0;
for (int i = min; i <= count / 2; i++) { //以2个人平分的分数为边界
if (count % i == 0) { //得分总数可以整除得分
score = i; //当前平均分
if (combine(ints, score, new ArrayList<>(), t - 1)) { //从最后一位开始计算（否则会出现问题）
res = score;
break;
}
}
}
System.out.println(res == 0 ? count : res); //分数平分不成功则输出总分
}
/**
* @param ints 篮球得分数组
* @param n 分数
* @param list 使用过的得分
* @param index 得分数组的索引
* @return
*/
public static boolean combine(int[] ints, int n, List<Integer> list, int index) {
if (n <= 0) { //分配的得分小于等于平均分
if (n == 0) {
for (Integer integer : list) { //将分配过的得分清0（此处不能用删除，否则会越界）
ints[integer] = 0;
}
return true;
}
}
for (int i = index; i >= 0; i--) {
if (n < 0 || Arrays.stream(ints).sum() == 0) { //得分小于0或者总得分等于0时跳出循环
break;
}
int x = ints[i];
if (x == 0) { //此得分失效时寻找下一个得分
continue;
}
list.add(i); //分配过的得分集合
if (combine(ints, n - x, list, i - 1)) { //分数获取成功后继续下一个分数分配
int count = Arrays.stream(ints).sum(); //当前得分数组中所剩的总得分
if (count == 0 || count % score != 0) { //剩余总分等于0或不能对得分进行整除则跳出循环
break;
}
combine(ints, score, new ArrayList<>(), ints.length - 1);
}
list.remove(list.size() - 1);
}
return Arrays.stream(ints).sum() == 0; //如果剩余总分等于0则表示分配成功
}
}
代码实现二：满分题解
package com.codernav.demo.hwod.exam;
import java.util.Arrays;
import java.util.Scanner;
/**
* @title MVP争夺战
* @Description 在星球争霸篮球赛对抗赛中，强大的宇宙战队，希望每个人都能拿到MVP。
* MVP的条件是，单场最高分得分获得者，可以并列，所以宇宙战队决定在比赛中，尽可能让更多的队员上场，且让所有有得分的队员得分都相同。
* 然而比赛过程中的每一分钟的得分都只能由某一个人包揽
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/14
*/
public class Main {
static int[] cnt = new int[51];
static int maxn = -1;
static int minn = 51;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
sc.nextLine();
String[] p = sc.nextLine().split(" ");
int[] ints = Arrays.stream(p).mapToInt(Integer::parseInt).toArray();
int total = 0;
maxn = Arrays.stream(ints).max().getAsInt();
minn = Arrays.stream(ints).min().getAsInt();
//原代码95分，唯一错误用例20 1 2 3 4 5 6 7 8 9 21 23 24 25 26 28 27 26 29
//所有这边的边界不能用t，只能用得分p的长度
for (int anInt : ints) {
cnt[anInt]++;
total += anInt;
}
for (int i = maxn; i <= total / 2; ++i) {
if (total % i == 0) {
dfs(total / i, 0, i, maxn);
}
}
System.out.println(total);
}
public static void dfs(int res, int sum, int target, int p) {
if (res == 0) {
System.out.println(target);
System.exit(0);
}
if (sum == target) {
dfs(res - 1, 0, target, maxn);
return;
}
for (int i = p; i >= minn; --i) {
if (cnt[i] > 0 && (i + sum) <= target) {
cnt[i]--;
dfs(res, sum + i, target, i);
cnt[i]++;
if (sum == 0 || (sum + i) == target) {
break;
}
}
}
}
}
© 版权声明
文章版权归作者所有，未经允许请勿转载。
相关文章
暂无评论...
❯
1. 本站博客内容及资源，原作者享有著作权，个人可以使用，但请勿用于商业用途。2. 所有文章可以转载、摘编、复制或建立镜像，但请注明原文链接。如有违反，追究法律责任。3. 举报邮箱：codernav@foxmail.com
