1

Решал такую задачу:

Тимофей решил организовать соревнование по спортивному программированию, чтобы найти талантливых стажёров. Задачи подобраны, участники зарегистрированы, тесты написаны. Осталось придумать, как в конце соревнования будет определяться победитель.

Каждый участник имеет уникальный логин. Когда соревнование закончится, к нему будут привязаны два показателя: количество решённых задач Pi и размер штрафа Fi. Штраф начисляется за неудачные попытки и время, затраченное на задачу.

Тимофей решил сортировать таблицу результатов следующим образом: при сравнении двух участников выше будет идти тот, у которого решено больше задач. При равенстве числа решённых задач первым идёт участник с меньшим штрафом. Если же и штрафы совпадают, то первым будет тот, у которого логин идёт раньше в алфавитном (лексикографическом) порядке.

Тимофей заказал толстовки для победителей и накануне поехал за ними в магазин. В своё отсутствие он поручил вам реализовать алгоритм быстрой сортировки (англ. quick sort) для таблицы результатов. Так как Тимофей любит спортивное программирование и не любит зря расходовать оперативную память, то ваша реализация сортировки не может потреблять O(n) дополнительной памяти для промежуточных данных (такая модификация быстрой сортировки называется "in-place").

Как работает in-place quick sort Как и в случае обычной быстрой сортировки, которая использует дополнительную память, необходимо выбрать опорный элемент (англ. pivot), а затем переупорядочить массив. Сделаем так, чтобы сначала шли элементы, не превосходящие опорного, а затем —– большие опорного.

Затем сортировка вызывается рекурсивно для двух полученных частей. Именно на этапе разделения элементов на группы в обычном алгоритме используется дополнительная память. Теперь разберёмся, как реализовать этот шаг in-place.

Пусть мы как-то выбрали опорный элемент. Заведём два указателя left и right, которые изначально будут указывать на левый и правый концы отрезка соответственно. Затем будем двигать левый указатель вправо до тех пор, пока он указывает на элемент, меньший опорного. Аналогично двигаем правый указатель влево, пока он стоит на элементе, превосходящем опорный. В итоге окажется, что что левее от left все элементы точно принадлежат первой группе, а правее от right — второй. Элементы, на которых стоят указатели, нарушают порядок. Поменяем их местами (в большинстве языков программирования используется функция swap()) и продвинем указатели на следующие элементы. Будем повторять это действие до тех пор, пока left и right не столкнутся. На рисунке представлен пример разделения при pivot=5. Указатель left — голубой, right — оранжевый.

Формат ввода В первой строке задано число участников n, 1 ≤ n ≤ 100 000. В каждой из следующих n строк задана информация про одного из участников. i-й участник описывается тремя параметрами:

уникальным логином (строкой из маленьких латинских букв длиной не более 20) числом решённых задач Pi штрафом Fi Fi и Pi — целые числа, лежащие в диапазоне от 0 до 109. Формат вывода Для отсортированного списка участников выведите по порядку их логины по одному в строке.

Пример 1

Ввод           Вывод   
5              gena
alla 4 100     timofey
gena 6 1000    alla
gosha 2 90     gosha
rita 2 90      rita
timofey 4 80

Учитель просит подкорректировать код: Нужно написать свой класс для отображения участника. (Подсказка: достаточно реализовать метод init для сохранения значений в атрибуты класса.) Использовать метод lt, который позволяет реализовать проверку на «меньше чем».

Но я не пойму как это реализовать.Очень прошу помочь Вот мой код:

def quicksort(nums):
    if len(nums) <= 1:
        return nums

    q = nums[len(nums) // 2]
    s_nums = []
    m_nums = []
    e_nums = []

    for n in nums:
        if n[1] > q[1]:
            s_nums.append(n)
        elif n[1] < q[1]:
            m_nums.append(n)
        else:
            if n[0] == q[0]:
                e_nums.append(n)
            elif n[2] != q[2]:
                s_nums.append(n) if n[2] < q[2] else m_nums.append(n)
            else:
                s_nums.append(n) if n[0] < q[0] else m_nums.append(n)

    return quicksort(s_nums) + e_nums + quicksort(m_nums)


def main():
    n = int(input())
    p = []
    for i in range(n):
        q = list(input().split())
        q[1] = int(q[1])
        q[2] = int(q[2])
        p.append(q)
    sort = quicksort(p)
    for s in sort:
        print(s[0])

4
  • а с чем именно проблемы? с быстрой сортировкой или с реализацией класса?
    – Zhihar
    7 ноя 2021 в 17:42
  • В тексте же описана процедура, которая не требует дополнительной памяти. Вот и возьмите реализацию разбиения Хоара хоть из википедии.
    – MBo
    7 ноя 2021 в 17:43
  • @Zhihar выделена проблема со строки q[1] = int(q[1]) 7 ноя 2021 в 17:43
  • так на этой строке проблемы нет
    – Zhihar
    7 ноя 2021 в 17:49

1 ответ 1

1

Вам нужно просто вставить правильное условие в сортировке. Я взял быструю сортировку здесь. Когда мы сравниваем элементы, то мы должны сравнить сначала Pi, потом Fi и в конце имя. Я решил для чистоты кода использовать датаклассы.

from dataclasses import dataclass
import random

@dataclass
class Person:
    name: str
    solved: int
    errors: int
    
    def __gt__(self, other):
        """
        "Больше", т.е. ниже в списке.
        У этого участника меньше Pi, больше Fi и имя в алфавите ниже.
        """
        if self.solved == other.solved:
            if self.errors == other.errors:
                return self.name > other.name
            return self.errors > other.errors
        return self.solved < other.solved
    
    def __lt__(self, other):
        """
        "Меньше", т.е. выше в списке.
        У этого участника больше Pi, меньше Fi и имя в алфавите выше.
        """
        if self.solved == other.solved:
            if self.errors == other.errors:
                return self.name < other.name
            return self.errors < other.errors
        return self.solved > other.solved
    

def quicksort(nums, left, right):
   if left >= right:
       return
 
   i, j = left, right
   pivot = nums[random.randint(left, right)]
 
   while i <= j:
       while nums[i] < pivot: 
           i += 1
       while nums[j] > pivot:
           j -= 1
           
       if i <= j:
           nums[i], nums[j] = nums[j], nums[i]
           i, j = i + 1, j - 1
           
   quicksort(nums, left, j)
   quicksort(nums, i, right)


def main():
    n = int(input())
    persons = []
    for _ in range(n):
        name, solved, errors = input().split()
        persons.append(
            Person(name, int(solved), int(errors))
        )
    
    quicksort(persons, 0, n - 1)
    for person in persons:
        print(person.name)


main()
8
  • ваша реализация сортировки не может потреблять O(n) дополнительной памяти для промежуточных данных
    – MBo
    7 ноя 2021 в 18:13
  • @MBo А каким образом она дополнительно потребляет? Уточните, пожалуйста. 7 ноя 2021 в 18:19
  • s_nums, m_nums, e_nums потребляют памяти в размере полного массива O(n). Там, где вы взяли код, далее идёт in-place версия, не использующая доп. память.
    – MBo
    7 ноя 2021 в 18:22
  • @MBo Увидел. Заменил, как Вы сказали: на "реализацию разбиения Хоара". 7 ноя 2021 в 18:24
  • Ваш алгоритм выдаёт ошибку Traceback (most recent call last): File "74f293de-d906-41b3-a32a-acf941c9f7cc", line 60, in <module> main() File "74f293de-d906-41b3-a32a-acf941c9f7cc", line 55, in main quicksort(persons) TypeError: quicksort() missing 2 required positional arguments: 'left' and 'right' 7 ноя 2021 в 18:39

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.