【MVP 争夺战】

MVP 争夺战

MVP 争夺战
知识点DFS搜索
时间限制:1s 空间限制:256MB 限定语言:不限
题目描述:
在星球争霸篮球赛对抗赛中,3 强大的宇宙战队,希望每个人都能拿到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

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<t; i++){
ints[i] = Integer.valueOf(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(int i=0; i<list.size(); i++){ //将分配过的得分清0（此处不能用删除，
否则会越界）
ints[list.get(i)] = 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 则表示分配成功
}
}

python解法：

import time
start = time.time()nums = [5,5,5,2,2,2,1,1,1]
# nums = [2,5,1,2,2,5,1,5,1]
# nums = [3,2,4,3,6]
def get_factors(num):factors = []for i in range(1, num+1):if num % i == 0:factors.append(i)return factors
sums = sum(nums)
factors = get_factors(sums)
Global_Target = []# 先加出来1个因子
# 然后把因子设为target，让后面的计算去拟合target，超于target的直接退出
def find_next_sum(cur_sum,cur_nums,target = None,match_num = 0):global Global_Targetif len(cur_nums) == 0:if target is None:return 0,0if (target * (match_num + 1) != sums):return 0,0if target not in Global_Target:print (f"hit {target}")Global_Target.append(target)return target,match_num#必须要把数全部用完才有max_match_nummax_match_num = 0max_target = targetfor i in range(len(cur_nums)):new_tar = cur_sum + cur_nums[i]#多个子数组if target is not None and target == new_tar:cur_target , cur_max_match_num = find_next_sum(0,cur_nums[:i] + cur_nums[i+1:],target = new_tar,match_num = match_num + 1)if cur_max_match_num > max_match_num:max_match_num = cur_max_match_nummax_target = cur_targetbreak#找到新的targetif target is None and new_tar in factors:cur_target , cur_max_match_num = find_next_sum(0,cur_nums[:i] + cur_nums[i+1:],target = new_tar)if cur_max_match_num > max_match_num:max_match_num = cur_max_match_nummax_target = cur_target#target越界if new_tar > sums / 2:continue#累加过程cur_target , cur_max_match_num = find_next_sum(new_tar,cur_nums[:i] + cur_nums[i+1:],target = target,match_num = match_num)if cur_max_match_num > max_match_num:max_match_num = cur_max_match_nummax_target = cur_targetreturn max_target,max_match_numcur_target , cur_max_match_num = find_next_sum(0,nums)
cur_max_match_num += 1
print (f"{cur_target},{cur_max_match_num}")        end = time.time()
print (f"time cost:{end - start}")