网易历届笔试题（11）

119 阅读 0 评论 79 点赞

我是靠谱客的博主震动飞机，这篇文章主要介绍网易历届笔试题（11），现在分享给大家，希望可以做个参考。

题目描述

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

输入描述:

复制代码

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

输出描述:

复制代码

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

示例1

输入

复制代码

输出

复制代码

1
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背包。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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);
}
}