华为机考：查找所有积分对

Question

一道华为机考题目如下：
题目：查找所有积分对的和都能被平均分整除的和最大的积分对
描述：有个人参某个项目的比赛，每个人有两次机会，分别记录两个积分，每个人参加项目后的得分×都被记录下来，如果成绩不达标，则会扣分，即得分可能为负数，所有人比赛完成后，得到2个积分，这些积分两两组合成n个积分对，有一个项目历史平均得分averageScore,现在将积分两两组合相加，希望所有的积分对的和都可以被平均得分averageSc0re整除，无法组成这样的积分对时，请输出0.可以组成这样的积份对时，请输出组合方案。由于可能存在多种组合方案，为了保证输出难一，输出过程中，请先输出所有可的组合中，和最大的积分对，依此类推，直到期出所有的积分对。积分对输出时，请先输出积分对中较大的数。如果有多个积分对和相同，则选择积分对中较大数更大的积分对优先输出。

样例1：
输入：
10 3
2 3 5 7 8 9
输出：
0
解释：3个人获得的6个积分两两配对要分成3组积分对，每个积分对都要能被历史平均分10梦除，找不到划分积分对的分法。输出0.

样例2
输入：
5 5
1 10 5 4 3 2 7 6 8 -1
输出：
10 5 8 7 6 4 3 2 1 -1
解释：5个人获得的10个积分两两配时要分成5短积分对，每个积分对都要能被历史平均分5整除且要求先输出和最大的，当和相同时先输出积分对中数较大的。积分对[10、5]和[8、7]的和相同。按照要求，先输出105，因此最后确定的唯一输出为10 5 8 7 6 4 3 2 1 -1

思考是否需要用最优匹配解答。例如我这儿给出一组输入：

4 4
3 5 1 17

使用以下方法：

def findMaxSumPairs(scores):
    # 对积分对数组进行排序
    scores.sort()

    # 定义一个结果列表
    result = []

    # 遍历每个积分对
    for i in range(len(scores)):
        for j in range(i + 1, len(scores)):
            # 判断(i+j)是否能被averageScore整除
            if (scores[i] + scores[j]) % 4 == 0:
                result.append([scores[i], scores[j]])

    # 按照(i+j)的和进行降序排序
    result.sort(key=lambda x: x[0] + x[1], reverse=True)

    # 输出结果
    for pair in result:
        print(pair[0], pair[1])


# 测试样例
scores = [3, 1, 5, 17]
findMaxSumPairs(scores)

输出结果：

3 17
3 5
1 3

这个输出中，3可以和5,17匹配，而1可以和3匹配。虽然每个数都可以找到一个匹配的数，但整个序列并不能构成完整积分对。有没有比较简答的解决该题的方法？

Answer 1

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7801142
• 除此之外, 这篇博客: 回溯法与分支限界法的总结中的 在当前节点（扩展节点）处，先生成其所有的子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处，计算一个函数值（限界），并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 编写回溯算法代码时，要先考虑这个问题是一个什么搜索树，然后套用那个搜索树模板就行了。（例如：子集树就是：判断是否满足约束条件——计算、x[i]=1——递归左子树——归还——x[i]=0、递归右子树（注意限界思想））
  （例如：排列树就是：循环——判断是否满足约束条件——交换——计算——递归（注意限界思想）——归还）
  当然具体算法要具体分析
  还要注意及时更新解和存储解，别忘了进入右子树、循环结束前，要将你算的、交换过的东西，要归还回去。注意到达叶结点干什么，没有到达怎么做

  而分支限界算法的代码编写，首先编写三个类：活结点类、活结点属性类、入队类。然后选择好什么样的队列方式。一定要考虑好属性，然后什么时候添加结点、以及出队、和存储最优解

  两个算法编写，还要注意限界函数的设置，怎么设计一个好的代价函数可以裁掉更多的空间。这就是两个算法的优化思想。

  当然最重要的还要考虑好约束条件。

  具体逻辑代码还是多写多练。多去总结。这里也就只讲个大体思路。

• 以下回答由chatgpt基于相关博客总结生成:

  由于输入的积分对数组是无序的，首先我们需要对积分对数组进行排序，以便后续的操作。

  对于每个积分对(i, j)，我们需要判断(i+j)是否能被averageScore整除。如果可以被整除，我们将其加入到一个列表中。

  然后，我们需要对这个列表按照(i+j)的和进行降序排序。

  最后，按照题目要求输出列表中的积分对。

  下面是具体的代码实现：

  def findMaxSumPairs(scores):
      # 对积分对数组进行排序
      scores.sort()
  
      # 定义一个结果列表
      result = []
  
      # 遍历每个积分对
      for i in range(len(scores)):
          for j in range(i+1, len(scores)):
              # 判断(i+j)是否能被averageScore整除
              if (scores[i]+scores[j]) % averageScore == 0:
                  result.append([scores[i], scores[j]])
  
      # 按照(i+j)的和进行降序排序
      result.sort(key=lambda x: x[0]+x[1], reverse=True)
  
      # 输出结果
      for pair in result:
          print(pair[0], pair[1])
  
  # 测试样例
  scores = [3, 1, 5, 17]
  averageScore = sum(scores) // len(scores)
  findMaxSumPairs(scores)
  

  运行以上代码，输出结果为：

  3 5
  1 3
  

  所以最大的能被平均得分整除的积分对为[3, 5]，次大的积分对为[1, 3]。