Skip to main content
Učilnica FRI 24/25
  • Home
  • More
Close
Toggle search input
English ‎(en)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
You are currently using guest access
Log in
Učilnica FRI 24/25
Home
Expand all Collapse all
  1. aps1uni
  2. Napredna urejanja
  3. Inverzije

Inverzije

Completion requirements
Opened: Monday, 15 April 2024, 12:00 AM
Due: Monday, 22 April 2024, 12:00 AM

Podan je seznam $N$ števil $x_i$. Paru indeksov $i$ in $j$, kjer je $i<j$ in $x_i > x_j$, rečemo inverzija. Inverzije so torej pari števil, ki niso v pravem vrstnem redu (naraščajoče urejen seznam nima inverzij). Napišite program, ki bo učinkovito izračunal število inverzij v podanem seznamu.

Namig: razmislite o prilagoditvi algoritma merge sort.

Omejitve podatkov:

  • $1 \leq N \leq 10^6$
  • $0 \leq x_i \leq 10^9$

Vhodni in izhodni podatki:

V prvi vrstici je podana velikost seznama $N$. V drugi vrstici so po vrsti s presledkom ločena števila $x_1, x_2, \ldots, x_N$.

Izpišite število inverzij v seznamu.

Primer vhoda:

6
7 2 4 2 1 5

Pravilen izhod:

9
You are currently using guest access (Log in)
Get the mobile app
Powered by Moodle
Obvestilo o avtorskih pravicah