Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 11.01.2024, 20:25   #1
Nicodim
Пользователь
 
Регистрация: 31.05.2023
Сообщений: 12
По умолчанию Программирование на Python число инверсий

Здравствуйте, помогите пожалуйста разобраться в задаче. Заранее благодарен!

Первая строка содержит число 1≤ n ≤ 10 в 5 степени, вторая - массив A[1....n], содержащий натуральные числа, не превосходящие 10 в 9 степени. Необходимо посчитать число пар индексов
1≤ i < j ≤ n, для которых A[i] > A[j]. (Такая пара элементов называется инверсией массива. Количество инверсий в массиве является в некотором смысле его мерой неупорядоченности: например, в упорядоченном по не убыванию массиве инверсий нет вообще, а в массиве, упорядоченном по убыванию, инверсию образуют каждые два элемента.)

Sample Input:

5
2 3 9 2 9

Sample Output:

2

Код:
GLOBAL_REPLACE_COUNT = 2




def merge(array: list, start: int, mid: int, end: int) -> None:

    
    global GLOBAL_REPLACE_COUNT

    l, m = 0, 0
    result = []

    while start + l < mid and m + mid < end:
        if array[start + l] <= array[mid + m]:
            result.append(array[start + l])
            l += 1
        else:
            result.append(array[mid + m])
            m += 1
           

    while start + l < mid:
        result.append(array[l + start])
        l += 1

    while m + mid < end:
        result.append(array[m + mid])
        m += 1

    for i in range(end - start):
        array[start + i] = result[i]


def merge_sort(array: list, start: int, end: int):

    if start + 1 < end:
        
        mid = int((start + end) / 2)

       ray, start, mid)

        
        merge_sort(array, mid, end)
        merge(array, start, mid, end)
        
        def main():
    
    length = int(input())
    array = list(map(int, input().split()))
    merge_sort(array, 0, len(array))

    print(GLOBAL_REPLACE_COUNT)


if __name__ == '__main__':
    main()
Nicodim вне форума Ответить с цитированием
Старый 12.01.2024, 06:49   #2
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,291
По умолчанию

Самое простое, взять книгу Тима Рафгардена "Совершенный алгоритм. Основы", ознакомиться с главой "3.2. Подсчет инверсий за время О(n log n)" и подправить merge_sort.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA на форуме Ответить с цитированием
Старый 12.01.2024, 22:05   #3
Nicodim
Пользователь
 
Регистрация: 31.05.2023
Сообщений: 12
По умолчанию

Благодарю за помощь!
Nicodim вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Программирование на Python Задача на программирование покрытие отрезками Nicodim Помощь студентам 2 29.12.2023 21:19
Программирование в Python fyz abkbvjyjdf Помощь студентам 1 17.12.2022 11:34
Программирование на Python fyz abkbvjyjdf Помощь студентам 11 14.12.2022 19:42
Программирование на python Семен_13 Python 7 17.10.2022 17:59
Программирование Python Белка и Стрелка Помощь студентам 1 29.05.2017 23:53