Задача на Python (Задача сапожника)

def minimize_penalty(orders):
    # Сортировка заказов по двум критериям: штрафу и времени выполнения
    orders.sort(key=lambda x: (x[1], x[0]))
 
    min_penalty = float('inf')  # Начальное значение минимального штрафа
    result = []  # Результат, содержащий последовательность заказов
    current_penalty = 0  # Текущий штраф
 
    for i, (days, penalty) in enumerate(orders):
        current_penalty += days * penalty
        # Если текущий штраф меньше минимального, обновляем результат
        if current_penalty < min_penalty:
            min_penalty = current_penalty
            result = [i + 1]  # Обновляем результат с новым заказом
        # Если текущий штраф равен минимальному, добавляем заказ в результат
        elif current_penalty == min_penalty:
            result.append(i + 1)
 
    return result
 
 
# Чтение входных данных
def read_input():
    test_cases = int(input())
    input_data = []
 
    for _ in range(test_cases):
        _ = input()  # Пропускаем пустую строку
        n = int(input())  # Количество заказов
        orders = []
        for _ in range(n):
            days, penalty = map(int, input().split())
            orders.append((days, penalty))
        input_data.append((n, orders))
 
    return input_data
 
 
 
 
# Основная функция для обработки всех тестовых блоков
def main():
    input_data = read_input()
 
    for n, orders in input_data:
        result = minimize_penalty(orders)
        print(*result)
 
        if input_data.index((n, orders)) < len(input_data) - 1:
            print()  # Разделитель для следующего тестового блока
 
 
if __name__ == "__main__":
    main()

from functools import cmp_to_key
for _ in range(int(input())):
    w = [(*map(int, input().split()), k+1) for k in range(int(input()))]
    w.sort(key=cmp_to_key(lambda x, y: x[0]*y[1]-y[0]*x[1] or x[2]-y[2]))
    print(*(x[2] for x in w))

for _ in range(int(input())):
    w = [(*map(int, input().split()), k+1) for k in range(int(input()))]
    print(*(x[2] for x in sorted(w, key=lambda x: (x[0] / x[1], x[2]))))