首页 > 试题广场 >

篮球队

[编程题]篮球队

热度指数：2949 时间限制：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

输出

算法知识视频讲解

波千鸟

Golang版，参考我之渺小

package main

import (
    "fmt"
    "sort"
)

func main() {
    var n int
    fmt.Scan(&n)
    a := make([]int, n)
    sum := 0
    for i:=0; i<n; i++ {
        fmt.Scan(&a[i])
        sum += a[i]
    }
    // 能力值倒序排列
    sort.Sort(sort.IntSlice(a))
    sort.Sort(sort.Reverse(sort.IntSlice(a)))
    res := 0
    // 01背包
    dp := make([]int, sum + 1)
    dp[0] = 1
    for i:=1; i<=sum; i++ {
        dp[i] = 0
    }
    for i:=0; i<n; i++ {
        for j:=sum; j>=a[i]; j-- {
            dp[j] = dp[j] + dp[j - a[i]]
            if (j > sum - j) && (j - a[i] < sum - j + a[i]) {
                res += dp[j - a[i]]
            }
        }
    }
    fmt.Println(res)
}

发表于 2021-08-17 10:51:29 回复(0)