用 Python 编写程序，查找任意排列获得的最大和

pythonserver side programmingprogramming更新于 2025/11/26 11:56:17

假设我们有一个数组 nums，另一个数组名为请求，其中请求[i] = [start_i, end_i]，这表示第 i 个请求要求 nums[start_i] + nums[start_i+1] + ... + nums[end_i-1] + nums[end_i] 的总和。我们必须在所有 nums 排列中找到所有请求的最大总和。答案可能非常大，因此返回它对 10^9+7 取模的结果。

因此，如果输入为 nums = [10,20,30,40,50] request = [[1,3],[0,1]]，则输出将为 190，因为如果我们像 [30,50,40,20,10] 那样排列，我们得到:从请求[0] :nums[1] + nums[2] + nums[3] = 50 + 40 + 20 = 110，从请求[1] :nums[0] + nums[1] = 30 + 50 = 80，因此总和为 110+80 = 190。

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

A := a new list
for对于请求中的每个请求 (s, e)，执行
- 在 A 末尾插入对 (s, 0)
- 在 A 末尾插入对 (e, 1)
对列表 A 进行排序
fr := 一个空映射
cnt := 0
n := A 的大小
i := 0
当 i < n 时，执行
- r := 1
- 当 i < n - 1 且 A[i+1] 与 A[i] 相同，则执行
  - r := r + 1
  - i := i + 1
- cnt := cnt + r
- if cnt - r > 0，则
  - 在 fr[cnt-r] 末尾插入 (pre, p-1)
    - pre := p
- 否则当 flag 与 1 相同时，则
  - cnt := cnt - r
  - 在 fr[cnt+r] 末尾插入 (pre, p)
  - pre := p+1
- i := i + 1
按相反顺序对列表 nums 进行排序
ks := 来自 fr 所有键列表的新列表
按相反顺序对列表 ks 进行排序
ans := 0
m := 10^9 + 7
i := 0
对于 ks 中的每个 k，执行
- 对于 fr[k] 中的每个对 (s, e)，执行
  - d := e - s + 1
  - ans := ans + (nums[从索引 i 到 i+d-1] 所有元素之和) * k
  - ans := ans mod m
  - i := i + d
返回 ans

示例

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

from collections import defaultdict
def solve(nums, requests):
   A = []
   for s, e in requests:
      A.append((s, 0))
      A.append((e, 1))
   A.sort()
   fr = defaultdict(list)
   cnt = 0

   n = len(A)
   i = 0
   while i < n:
      r = 1
      while i < n - 1 and A[i+1] == A[i]:
         r += 1
         i += 1
      p, flag = A[i]
      if flag == 0:
         cnt += r
         if cnt - r > 0:
            fr[cnt-r].append((pre, p-1))
         pre = p
      elif flag == 1:
         cnt -= r
         fr[cnt+r].append((pre, p))
         pre = p+1
      i += 1

   nums.sort(reverse=True)
   ks = list(fr.keys())
   ks.sort(reverse=True)
   ans = 0
   m = 10**9 + 7
   i = 0
   for k in ks:
      for s, e in fr[k]:
         d = e - s + 1
         ans += sum(nums[i:i+d]) * k
         ans %= m
         i += d
   return ans

nums = [10,20,30,40,50]
requests = [[1,3],[0,1]]
print(solve(nums, requests))