网易历届笔试题（11）

题目描述

小Q是篮球训练队的教练，篮球队新加入了N名队员，第i名队员的篮球水平值为ai。
小Q现在要把他们按照以下的要求分为A队和B队进行训练:
1、A队的队员水平值之和严格大于B队的队员水平值之和
2、对于A队中的任意一名队员，如果把他分配到B队，A队的水平值之和就会严格小于B队的水平值之和。
3、每个队员必须要加入一个队伍
小Q现在想知道有多少种方案可以按照以上要求完成分队。

输入描述:

输入包括两行, 输入的第一行为一个正整数n(2 <= N <= 50), 表示队员的数量。
第二行包括N个正整数 ai(1 <= ai <= 6 x 104), 表示每名队员的篮球水平值, 以空格分割。

输出描述:

输出一个正整数, 表示方案数。

示例1

输入

4
5 4 7 6

输出

2

备注：比较好的一道题，这里参考了我之渺小大佬的解法。

思路：根据题意，A堆总重量严格大于B，但移动A堆任意一个苹果到B，A堆总重量严格小于B，说明，A和B的重量差一定小于A里面苹果重量的最小值的2倍，我们可以从大到小的枚举A堆里的最小值，假设枚举到w[i]，比w[i]小的肯定都在B那里，比w[i]大的就开始01背包，01背包的结果出来之后，统计一下sum(A)-sum(B)小于2 * w[i]有多少种情况，如果我们按照能力值arry从大到小排序，那么枚举过程相当于一次01背包。

import java.util.*;
public class Main{
public static void main(String[] args){
int n;
int sum=0;
long ans=0;
Scanner in=new Scanner(System.in);
n=in.nextInt();
int[] a=new int[n];
for(int i=0;i<n;i++){
a[i]=in.nextInt();
sum+=a[i];
}
Arrays.sort(a);
int[] dp=new int[sum+1];
dp[0]=1;
for(int i=n-1;i>=0;i--){
for(int j=sum;j>=a[i];j--){
dp[j]+=dp[j-a[i]];
if(j>sum-j && j-a[i]<sum-j+a[i])
ans+=dp[j-a[i]];
}
}
System.out.println(ans);
}
}

最后

以上就是震动飞机为你收集整理的网易历届笔试题（11）的全部内容，希望文章能够帮你解决网易历届笔试题（11）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。