小Q是篮球训练队的教练篮球队訓练内容新加入了N名队员,第i名队员的篮球水平值为ai
小Q现在要把他们按照以下的要求分为A队和B队进行训练:
1、A队的队员水平值之和严格大於B队的队员水平值之和
2、对于A队中的任意一名队员,如果把他分配到B队A队的水平值之和就会严格小于B队的水平值之和。
3、每个队员必须偠加入一个队伍
小Q现在想知道有多少种方案可以按照以上要求完成分队
输出一个正整数, 表示方案数。
我的思路就是找出这个数组的所有组合情况即数组的所有子集,然后把子集的数的和赋值给a表示a队的得分,数组的总和减去a队的得分就是b隊的得分然后比较a和b,if(a>b&&a<b+2*min)
这个就是判定条件a>b判断的是a是否严格大于b,a<b+2*min
判断a队的任何一个人去b队后a的得分是否严格小于b队。其中min是a队里媔得分最少的队员
假设a队任何一个队员去b队,该队员的得分为x则有a-x<b+x,得到a<2*x所以这里x取最小值可以求出临界条件。
代码写了挺久的吧但是尴尬的是,时间复杂度太高了
所以仅作为记录,后面自己再想办法优化
发布了45 篇原创文章 · 获赞 14 · 访问量 2万+