首页 > 试题广场 >

篮球队

[编程题]篮球队

热度指数：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

输出

算法知识视频讲解

Python

麦田201810281321172

#coding:utf-8
n = int(input())
arrs = list( map(int,input().split()))
arrs = sorted(arrs,reverse=True)
all_sum = sum(arrs)
res = 0
dp = [[0 for i in range(all_sum+1)] for i in range(2)]
for i in range(all_sum+1):
    dp[0][i] = 0
dp[0][0] = 1
for i in range(0,n):
    for j in range(1,all_sum+1):
        dp[1][j] = dp[0][j]
        if arrs[i] <= j:
            dp[1][j] = dp[1][j] + dp[0][j-arrs[i]]
            if j>all_sum-j and j-arrs[i]<all_sum-j+arrs[i]:
                res = res + dp[0][j-arrs[i]]
    for j in range(1,all_sum):
        dp[0][j] = dp[1][j]
print(str(res))

用python照着通过的C++打的，居然只通过50%，时间差这么大吗？

发表于 2019-08-15 00:52:58 回复(1)