用 Python 编写的分配重复整数的程序

pythonserver side programmingprogramming更新于 2025/12/7 22:04:17

假设我们有一个数组 nums，最多有 50 个唯一值。我们还有另一个名为"quantity"的数组，其中"quantity[i]"表示第 i 位顾客订购的商品数量。我们必须检查是否有可能分配 nums，使得

第 i 位顾客恰好获得"quantity[i]"个商品，
第 i 位顾客获得的价值都是相等的，并且
所有顾客都满意。

因此，如果输入为 nums = [5,1,2,2,3,4,4,3,3] quantity = [2,2,3]，则输出将为 True，因为两个顾客各想要两个元素，因此他们可以得到 [2,2] 和 [4,4]，而第三个顾客想要三个商品，他们可以得到 [3,3,3]，因此所有人都满意。

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

定义一个函数 util() 。它将采用 i、cntr
如果 i 与数量大小相同，则
- 返回 True
temp_counter := 复制 cntr
对于 cntr 中的每个 cnt，执行
- 如果 cnt >= 数量[i]，则
  - temp_counter[cnt] := temp_counter[cnt] - 1
  - 如果 temp_counter[cnt] 与 0 相同，则
    - 从中删除第 cnt 个元素temp_counter
  - rem := cnt - quantile[i]
  - temp_counter[rem] := temp_counter[rem] + 1
  - 如果 util(i+1, temp_counter) 为真，则
    - 返回 True
  - temp_counter[rem] := temp_counter[rem] - 1
  - 如果 temp_counter[rem] 与 0 相同，则
    - 从中删除第 rem 个元素temp_counter
- temp_counter[cnt] := temp_counter[cnt] + 1
返回 False
从 main 方法，执行以下操作
cnt := map 保存 nums 中存在的所有数字频率的频率
按相反顺序对数量进行排序
返回 util(0, cnt)

示例

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

from collections import Counter
def solve(nums, quantity):
   def util(i, cntr):
      if i == len(quantity):
         return True

      temp_counter = cntr.copy()
      for cnt in cntr:
         if cnt >= quantity[i]:
            temp_counter[cnt] -= 1
            if temp_counter[cnt] == 0:
               temp_counter.pop(cnt)
         rem = cnt - quantity[i]
         temp_counter[rem] += 1

         if util(i+1, temp_counter):
            return True

         temp_counter[rem] -= 1
         if temp_counter[rem] == 0:
            temp_counter.pop(rem)
         temp_counter[cnt] += 1

      return False

   cnt = Counter(Counter(nums).values())
   quantity.sort(reverse=True)
   return util(0, cnt)

nums = [5,1,2,2,3,4,4,3,3]
quantity = [2,2,3]
print(solve(nums, quantity))