用 Python 编写程序，找出没有冲突的最佳球队

pythonserver side programmingprogramming更新于 2025/11/30 2:52:17

假设我们有两个列表，分别称为 scores 和 ages，其中 scores[i] 和 ages[i] 代表篮球比赛中第 i 位球员的得分和年龄。我们想选出总得分最高的球队。这里球队的得分是球队中所有球员得分的总和。但我们不允许比赛中出现冲突。如果年轻玩家的得分严格高于年长玩家，则存在冲突。

因此，如果输入为 scores = [5,7,9,14,19], ages = [5,6,7,8,9]，则输出将为 54，因为我们可以选择所有玩家。

为了解决这个问题，我们将遵循以下步骤 −

sa := 分别从 ages 和 scores 中取出元素 a 和 s 形成的对列表
对列表 sa 进行排序
scores := 从 sa 中创建分数列表
maxScore := 0
n := scores 的大小
dp := 长度为 n 的数组并用 0 填充
对于范围为 0 到 n - 1 的 i，执行
- score := scores[i]
- dp[i] := score
- 对于 j 在 0 到 i - 1 范围内的情况，执行
  - 如果 scores[j] <= score，则
    - dp[i] := dp[i] 和 dp[j] + score 中的最大值
- maxScore := maxScore 和 dp[i] 中的最大值
返回 maxScore

示例

让我们看看下面的实现以便更好地理解 −


def solve(scores, ages):
   sa = [[a,s] for a,s in zip(ages,scores)]

   sa.sort()
   scores = [s for a,s in sa]

   maxScore = 0
   n = len(scores)
   dp = [0] * n

   for i in range(n):
      score = scores[i]
      dp[i] = score

      for j in range(i):
         if scores[j] <= score:
            dp[i] = max(dp[i],dp[j] + score)
      maxScore = max(maxScore, dp[i])

   return maxScore

scores = [5,7,9,14,19]
ages = [5,6,7,8,9]
print(solve(scores, ages))