[C++] Ilość inwersji

[mario765i]

Witam! Mam do napisania program takiej treści: Na wejściu w pierwszym wierszu podajemy liczbę n (1<=n<=10^6), w drugim wierszu podajemy permutację w postaci n liczb. Na wyjściu program ma wyświetlić liczbę inwersji w podanej permutacji. Oto napisany przeze mnie kod:

Kod: Zaznacz cały

#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);

    int tab[n];
    for (int i=0; i<n; i++)
    {
        scanf("%d",&tab[i]);
    }

	int ile_razy = n-1;
	int liczba_inwersji = 0;

	while (ile_razy > 0)
	{
		ile_razy--;

		for (int i=0; i<n-1; i++)
		{
			if ( tab[i] > tab[i+1] )
			{
                liczba_inwersji++;
				swap( tab[i], tab[i+1] );
			}
		}
	}

	printf("%d",liczba_inwersji);

	return 0;
}

Napisany przeze mnie program działa poprawnie, ale po wrzuceniu go na sprawdzarkę dostaję komunikat "time limit exceeded". I tu jest moja prośba: Mógłby ktoś poprawić mi ten program, tak aby przeszedł test sprawdzarki?

[adambak]

Twój program ma złożoność rzędu \(\displaystyle{ O(n^2)}\), co dla takich danych jest niedopuszczalne.. Musisz zejść do \(\displaystyle{ O(n\log n)}\), ale to nie jest trywialne.. tutaj coś więcej napisałem na ten temat: 267284.htm
właściwie to bardzo dużo tam powiedziałem.. jeśli jednak jest to dla Ciebie niezrozumiałe (bo z tego co wiem to zaczynasz przygodę z programowaniem, więc może to nie być zrozumiałe), to nie ma sensu żebyś dalej się z tym męczył, a tymbardziej - żeby ktoś to za Ciebie pisał..