C# algoritmus pro počet inverzí

C# algoritmus pro počet inverzí

Newbie

18. 3. 2011 #1

Zdravím,

dostal jsem za úkol stvořit program, kterej na vstupu dostane soubor s posloupností a vrátí kolik obsahuje inverzí.

Přesné zadání:

Je dána posloupnost celých čísel P1 ... PN. Čísla Pi a Pj jsou v inverzi, pokud i < j a zároveň Pi > Pj. 

Inverze je tedy porucha ve vzestupném uspořádání posloupnosti. Vašim úkolem je zjistit, kolik inverzí posloupnost obsahuje.



Vstupní posloupnost je uložena v textovém souboru cisla.in, kde na prvním řádku je číslo N 

a na druhém řádku následuje N celých čísel v desítkovém zápisu oddělených mezerami. 

Počet inverzí vypište na standardní výstup (v desítkovém zápisu).



Čísla mohou být i záporná a vejdou se do 32-bitového integeru.

 Čisel v poslounosti je maximálně 100 000 a počet inverzí se také vejde do 32-bitového integeru. 

Vstupní soubor se vejde do operační paměti (i několikrát).



Příklad:

cisla.in

  5

  4 5 3 1 2

std. výstup:

  8

stvořil jsem 2 řešení
#1

http://pastebin.com/DUvRbDz1

http://pastebin.com/641Ciahc

1. je na bázi merge sortu prakticky okopírovaný odsud

http://ksp.mff.cuni.cz/tasks/19/solution5.html#task5

2. je co mě napadlo jako první, při vkládání kontroluju kolik čísel dříve vložených je větších

Obě řešení na nějakých vstupech, které neznám, vrací údajně špatné výsledky.

Neměl by někdo nápad jak to vyřešit?

Díky.

Nahlásit jako SPAM

IP: 94.113.85.–

sh00ter 0

Newbie

18. 3. 2011 #2

Tak nakonec vyřešeno, chyba u prvního řešení byla na řádku 58, 100 000 jsem si převed na byte :D druhé se nakonec (nečekaně) projevilo jako neefektivní.

Nahlásit jako SPAM

IP: 94.113.85.–