Блог

Главная - Вопросы по программированию - Как быстрее считать инверсии

Как быстрее считать инверсии

#c #inversion

#c #инверсия

Вопрос:

Я пытаюсь ускорить работу моей программы подсчета инверсий, поскольку я постоянно получаю TLE. Я использовал C , и это мой код

 #include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
    int n;
    int count = 0;
    cin >> n;
    int arr[n];
    for(int i = 0; i < n; i  )
    {
        cin >> arr[i];
    }
    for(int i = 0; i < n - 1; i  )
    {
        for(int j = i   1; j < n; j  )
        if(arr[i] > arr[j])
        {
            count  ;
        }
    }
    cout << count;
}

Помогите, пожалуйста!

Комментарии:

1. найдите что-то вроде «алгоритм для подсчета инверсий» в вашем любимом движке для лучшего подхода?

2. Вероятно, вам следует использовать файл заголовка #include<cstdio> вместо #include <stdio.h> . #include <stdio.h> является заголовочным файлом C.. Или просто отбросьте его полностью.

3. @GenoC или просто удалите это, поскольку оно не используется.

4. Ваш алгоритм работает медленно, потому что это тривиальный O(n^2) подход грубой силы. Существует стратегия сортировки слиянием, подобная стратегии «разделяй и властвуй», которая делает это O(nlogn) вовремя. Найдите его, он легко доступен в Интернете.

5. @swag2198 значит, это совершенно новый алгоритм, которому я должен научить себя? Я действительно в замешательстве здесь .. D: