主页 / 问题 / 1593047
Accepted
Pou220
Asked:2024-09-06 23:51:20 +0000 UTC2024-09-06 23:51:20 +0000 UTC

如何加速Python中的这段代码？

  • 772

问题：课程结束时，有 n 个学生向基里尔提出问题，其中他总共有 m 个问题。每个学生都希望得到a题，如果他得到的题少，即b题，他就会生气(a − b)^2怒。每项任务只能分配给一名学生。基里尔真的不想激怒他心爱的学生，所以他请求你帮助减少课堂上的总愤怒。

def angry(m, n, List):
    numb = 0
    for i in range(m):
        List.sort(reverse=True)
        List[0] -= 1
    for i in range(n):
        numb += List[i] ** 2 
    return numb

m, n = map(int, input().split())
a = list(map(int, input().split()))

# Вывод минимальной злости
print(angry(m, n, a) % (2 ** 64))

也尝试过

def angry(m, n, List):
    for i in range(m):
        List.sort(reverse=True)
        List[0] -= 1
    return sum([x ** 2 for x in List])

m, n = map(int, input().split())
a = list(map(int, input().split()))

# Вывод минимальной злости
print(angry(m, n, a) % (2**64))

错误：“超出最长操作时间。 ”

我怎样才能加速这段代码以使最终结果相同？

python

3 个回答

  1. 为了解决这个问题，可以使用堆。堆允许您在高效的时间内检索最大元素，然后将其以减少的值返回到堆。这会将运行时间减少到 O(m log n) 而不是 O(m * n log n)。

    PS 如果你的代码保持原样，将很难优化，因此你需要更改算法。

    例子：

    import heapq

def angry(m, n, tasks):
    # Превратим список задач в max-кучу через использование отрицательных значений
    heap = [-x for x in tasks]
    heapq.heapify(heap)
    
    # Раздаем задачи
    for _ in range(m):
        # Извлекаем наибольшее количество задач
        max_tasks = heapq.heappop(heap)
        # Уменьшаем его на 1 и кладем обратно в кучу
        heapq.heappush(heap, max_tasks + 1)  # т.к. max_tasks отрицательное, прибавляем 1

    # Считаем итоговую злость
    total_anger = sum(x ** 2 for x in heap)
    
    # Возвращаем результат с нужным модулем
    return -total_anger % (2 ** 64)

# Чтение входных данных
m, n = map(int, input().split())
tasks = list(map(int, input().split()))

# Вывод минимальной злости
print(angry(m, n, tasks))
    • 0

  2. 不确定，但以防万一：

    import os

print("-" * 50 + "\nСуммарная злость в классе:\n" + "-" * 50)

def minimize_anger(n, m, a):
 # Если задач меньше, чем студентов, то невозможно удовлетворить всех:
 if m < n: return "Невозможно удовлетворить всех студентов"

 # Изначально все студенты получают по одной задаче:
 tasks_per_student = [1] * n
 remaining_tasks = m - n

 # Распределяем оставшиеся задачи:
 for i in range(n):
  if remaining_tasks == 0: break
  tasks_per_student[i] += 1
  remaining_tasks -= 1

 # Вычисляем суммарную злость:
 total_anger = sum((a - tasks_per_student[i]) ** 2 for i in range(n))
 return total_anger

# Пример использования:
n = 5  # количество студентов
m = 10  # количество задач
a = 3  # желаемое количество задач для каждого студента

print("Количество студентов:", n)
print("Количество задач:", m)
print("Желаемое количество задач для каждого студента:", a)
print("Минимизированная злость в классе:", minimize_anger(n, m, a))

print("\nНажмите любую клавишу для продолжения...")
os.system("pause > nul" if os.name == "nt" else "read > /dev/null")
    • 0
  3. Best Answer

    在限制条件下，任务数量最多可达20亿。没有足够的时间将它们一一分发。

    如果两个学生收到任务并且他们的剩余坏度（a i - b i）相差超过 1，那么一项任务可以从邪恶程度较低的任务转移到邪恶程度较高的任务，整体坏度将会降低。解决方案应该是这样的：某人根本不接收任务，而接收任务的人接收任务，以便恶意分布尽可能均匀。从这一点来看，问题的解决方案是正确的：选择最邪恶的一个，给他一个任务，更新他的邪恶并重复，直到任务结束或直到没有邪恶的留下。但正如已经说过的，一次分配一项任务是一条死胡同。

    让三个学生提出六个问题，两个学生提出四个问题，两个学生提出三个问题。任务数量m = 21。让我们对请求进行排序：

            * * *
        * * *
    * * * * *     m = 21
* * * * * * *
* * * * * * *
* * * * * * *

    根据身高将它们分为几组：

            3 3 3
        3 3 3
    2 2 3 3 3     m = 21
1 1 2 2 3 3 3
1 1 2 2 3 3 3
1 1 2 2 3 3 3

    您需要将最高的一组降低到第二高的高度。这需要六项任务。我们有他们：

        2 2 3 3 3
1 1 2 2 3 3 3     m = 15
1 1 2 2 3 3 3
1 1 2 2 3 3 3

    让我们组合相同高度的组：

        2 2 2 2 2
1 1 2 2 2 2 2     m = 15
1 1 2 2 2 2 2
1 1 2 2 2 2 2

    我们再次想要切断最高的组。需要五项任务。他们是。剪切和合并组：

    1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1     m = 10

    没有足够的任务来削减该组。让我们删除尽可能多的行（一）并从一行中删除剩余的任务（三）：

          1 1 1 1
1 1 1 1 1 1 1     m = 0

    没有像上面这样的图片；在一组中，每个人的身高应该相同。您需要创建两个组：

          2 2 2 2
1 1 1 2 2 2 2     m = 0

    由于没有剩余任务，我们停止循环并计算剩余的愤怒。

    程序的复杂度为 O(n·log n)。

    一名请求为零的学生已被添加到最初的恶劣名单中。这是必要的，以便最后剩余组的处理与其余组没有不同。

    import itertools

m, n = map(int, input().split())
a = list(map(int, input().split()))
a.append(0)

stack = list((a, sum(1 for _ in g)) for a, g in itertools.groupby(sorted(a)))

while m > 0 and len(stack) >= 2:
    a1, w1 = stack[-1]
    a2, w2 = stack[-2]
    h = a1 - a2
    if m >= h * w1:
        stack.pop()
        stack.pop()
        stack.append((a2, w1 + w2))
        m -= h * w1
    else:
        q, r = divmod(m, w1)
        stack.pop()
        stack.append((a1 - q - 1, r     ))
        stack.append((a1 - q    , w1 - r))
        m = 0

print(sum(a * a * w for a, w in stack) % 2 ** 64)
    • 0

相关问题