首页 > 试题广场 >

篮球队

[编程题]篮球队

热度指数：3005 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

4
5 4 7 6

输出

算法知识视频讲解

Java

LHospitals

//参照前面的各位大佬 加了更易懂的解释
//01背包问题

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        int[] arr = new int[len];
        long sum = 0;
        for (int i = 0; i < len; i++){
            arr[i] = in.nextInt();
            sum += arr[i];
        }
        Arrays.sort(arr);
        long ans = 0;
        long[] dp = new long[(int)sum + 1];
        // 分配初始值
        dp[0] = 1;
        for (int i = len - 1; i >= 0; i--){
            // j代表B队的当前总价值，j - arr[i]代表A队总价值
            for (int j = (int)sum; j >= arr[i]; j--){
                // 加上i的总价值
                dp[j] += dp[j - arr[i]];
                // 如果交换后B > A(j > sum - j)   交换前A > B(sum - (j - arr[i]) > j - arr[i])，
                if (j > sum - j && sum - (j - arr[i]) > j - arr[i]){
                    ans += dp[j - arr[i]];
                }
            }
        }
        System.out.println(ans);
    }

}

发表于 2020-08-06 11:48:09 回复(0)

Java

locherry

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        long n_sum = 0;
        for (int i = 0; i < n; i++){
            arr[i]=sc.nextInt();
            n_sum += arr[i];
        }
        solution(arr,n,n_sum);
    }
    private static void solution(int[] arr,int n,long n_sum) {
        long ans = 0;
        //降序
        Arrays.sort(arr);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i: arr){
            list.add(i);
        }
        Collections.reverse(list);
        int[] newArr = new int[arr.length];
        for (int i = 0; i < list.size(); i++){
            newArr[i]=list.get(i);
        }
        long[][] dp = new long[2][(int)n_sum+1];
        dp[0][0] = 1;//0个商品，总价值数0的方案数
        for (int j = 1; j <= n_sum;j++){
            dp[0][j]=0;//0个商品，总价值数为j的方案数量为0
        }
        for (int i = 0; i < n; i++){
            for (int j = 1; j < n_sum; j++){
                dp[1][j]=dp[0][j];//未加入商品价值
                if (j-newArr[i]>=0){
                    dp[1][j]+=dp[0][j-newArr[i]];
                    if (j>n_sum-j&&j-newArr[i]<n_sum-j+newArr[i]){
                        ans += dp[0][j-newArr[i]];
                    }
                }
            }
            //更新
            for (int j = 1; j < n_sum; j++){
                dp[0][j] = dp[1][j];
            }
        }
        System.out.println(ans);
    }
}

编辑于 2019-08-19 11:53:15 回复(0)