1

Нужно найти количество инверсий, если Число1 больше числа2 и индекс числа1 меньше индекса числа2 то это будет являться инверсией

Условие задачи

Условие задачи

n = int(input())
list1 = list()
res = 0
for range1 in range(n):
    k=int(input())
    list1.append(k)
for range2 in range(len(list1)):
    for range3 in range(range2+1,len(list1)): 
        if list1[range2] > list1[range3] and range2 < range3:
            res+=1
print(res)
4
  • 1
    а можете дать ссылку на проверяющую систему ?
    – n1tr0xs
    24 янв 2021 в 17:38
  • @n1tr0xs я бы с радостью но хакерранк где задания для сдачи сессии и вы не сможете зайти
    – Derzh
    24 янв 2021 в 19:23
  • вот этот код прошёл Этот же код у Вас был с самого начала, и он не должен проходить при n=100000
    – MBo
    30 янв 2021 в 14:41
  • @MBo ,а я перепутал просто у меня две одинаковых задачи только ограничения разные, извиняюсь
    – Derzh
    30 янв 2021 в 14:57

3 ответа 3

1

Я бы сделал так:

arr = []
res = 0
for _ in range(int(input())):
    n = int(input())
    res += sum(el > n for el in arr)
    arr.append(n)

print(res)
1
  • всё равно пишет что нужно быстрее
    – Derzh
    24 янв 2021 в 16:08
1

Количество элементов 10^5 обычно подразумевает, что решение за квадрат не пройдёт, а вот O(nlogn) - устроит.

Для достижения такой сложности можно использовать сортировку слиянием. В процедуре слияния (merge) есть такой шаг, когда в результат пишется элемент из правой половины. Вот в этот момент нужно к (локальному) счётчику инверсий добавить количество ещё неиспользованных элементов левой половины.

invcount = 0
...
if left[i] <= right[j]:
      a[k] = left[i]
      i += 1
      k += 1    
else:
      a[k] = right[j]
      invcount += length(left) - i
      j += 1
      k += 1    
...
return invcount

А в рекурсивной процедуре mergesort нужно сложить количество инверсий в левой половине, количество в правой, и количество инверсий, возникающих при слиянии (то, что возвращает merge)

... разделение массива на две части
return mergesort(left) + mergesort(right) + merge(left, right)
2
  • я только не давно начал учить питон и не совсем вас понимаю, можно объяснить это чуть попроще?
    – Derzh
    24 янв 2021 в 23:55
  • @Derzh Значит, Вам нужно изучить работу алгоритма сортировки слиянием
    – MBo
    25 янв 2021 в 5:27
0

Вариант 1:

A = list(int(input()) for _ in range(int(input())))
c = 0
for i in range(len(A)):
    for j in range(i+1, len(A)):
        if A[i] > A[j]:
            c += 1
print(c)

Вариант 2:

A = list(int(input()) for _ in range(int(input())))
print(sum(A[i]>A[j] for i in range(len(A)) for j in range(i+1, len(A))))

Вариант 3:

A = list(int(input()) for _ in range(int(input())))
print(len([1 for i in range(len(A)) for j in range(i+1, len(A)) if A[i]>A[j]]))
3
  • 1
    можно написать sum(A[i]>A[j] ...)
    – Danis
    24 янв 2021 в 15:53
  • @Danis спасибо за подсказку
    – n1tr0xs
    24 янв 2021 в 15:54
  • @n1tr0xs всё равно не проходит по времени, возможно нужно без фор это решить
    – Derzh
    24 янв 2021 в 16:10

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

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