Найти правильный порядок чисел - Python 3,7 - PullRequest
Новая
       16

Найти правильный порядок чисел - Python 3,7

0 голосов
/ 11 апреля 2020

Я работаю над решением, которое показано ниже: у меня есть 2 несортированных списка, и мне нужно найти способ, который может дать мне значение, сравнивая числа из первого списка со вторым списком. правила таковы: - игрок может сражаться только с одиночным игроком - игрок может выиграть, только когда его / ее сила строго больше, чем у противника

Формат ввода - Первая строка ввода состоит из из числа тестовых наборов, T - Первая строка каждого тестового набора состоит из количества членов, которое может иметь каждая команда, N. - Вторая строка каждого тестового набора состоит из N разделенных пробелом целых чисел, представляющих степень первого команда - третья строка каждого теста состоит из N разделенных пробелом целых чисел, представляющих силу второй команды

Я написал следующий код: 

def get_info(n,tg,op):
    cnt = 0
    for i in range(n):
        for j in range(len(op)):
            if tg[i]>op[j]:
                cnt+=1
                op.pop(j)                
                break    
    return cnt

def main():
    t=int(input())
    l = []
    for i in range(t):
        n=int(input())
        tg=list(map(int,input().split()))
        op=list(map(int,input().split()))    
        # cnt=0
        tg.sort(reverse=True)    
        op.sort(reverse=True)
        res = get_info(n,tg,op)
        l.append(res)
    print(*l,sep='\n')


main()

Вход и выход как следующим образом: 

1
10
3 6 7 5 3 5 6 2 9 1
2 7 0 9 3 6 0 6 2 6
7

Ограничения следующие:

Ограничения 1 <= T <= 100000 1 <= N <= 100000 0 <= Мощность клинка <= LLONG_MAX </p>

Мне удалось пройти большинство тестовых случаев, но когда список увеличился, программа перестала работать, а время извлечения превысило

Это можно решить с помощью Bisect или двух po интер в Python для лучших результатов?

Пожалуйста, сообщите

1 Ответ

1 голос
/ 19 апреля 2020

Вы повторяете ненужные каждый раз с начала списка. Предположим, что ваши списки выглядят так: 

[12, 11, 10, 5, 4, 4] #tg
[13, 13, 13, 2, 1, 0] #op

Для 12 вы l oop до 2 во втором списке. Для 11 вы l oop до 1 и для 10 вы l oop до 0. Несмотря на то, что вы вытолкнули элемент, вы сравниваете 12,11,10 со всеми 13, то есть 9 сравнений. Поскольку вы уже знаете, что 13> 12, нет необходимости сравнивать 11 или 10 с 13, что экономит вам 6 сравнений. Это потому, что вы отсортировали и знаете, что каждое последующее число будет меньше любого числа, оставшегося от последнего элемента списка операций.

Зная это, вы можете воспользоваться преимуществом, сохранив ненужные сравнения, начав со следующего элемента список операций: 

from itertools import islice
def get_info(n,tg,op):
    cnt = 0
    start_index = 0
        for index, tg_element in enumerate(tg):
            for op_element in islice(op,start_index,None):
                start_index += 1
                if tg_element > op_element:
                    cnt += 1
                    break    
    return cnt

Сложность вашего алгоритма была излишне в O (n ^ 2).

...