Rezolvare completă PbInfo #1715 Inversiuni

Ludwig are o permutare p=(p[1],p[2],...,p[N]) a mulțimii {1,2,..,N} și o masă pe care putea așeza numerele din permutare. Ludwig ia primul număr din permutare, adică p[1], și îl așează pe masă. Al doilea număr, p[2], îl pune fie în stânga lui p[1], fie în dreapta lui p[1]. La fiecare pas, dacă s-au așezat pe masă deja numerele p[1], p[2], …, p[i], atunci numărul p[i+1] este pus fie în stânga numerelor deja așezate, fie în dreapta lor.

Cerința

Ajutați-l pe Ludwig să determine o modalitate de așezare a întregii permutări pe masă astfel încât în final să se obțină o nouă permutare care are un număr minim de inversiuni.

Date de intrare

Fișierul de intrare inversiuni.in conține pe prima linie numărul natural N, iar pe linia a doua, separate prin câte un spațiu, numerele p[1], p[2], …, p[N].

Date de ieșire

Fișierul de ieșire inversiuni.out va conține un singur număr natural reprezentând numărul minim de inversiuni care se pot obține.

Restricții și precizări

  • 1 ≤ N ≤ 200 000
  • O inversiune în permutare este o pereche de indici (i,j) cu i<j și p[i]>p[j]. De exemplu, permutarea p=(3,2,1,4) are ca inversiune perechea de indici (1,3) pentru că p[1]>p[3]; o altă inversiune este perechea de indici (2,3) pentru că p[2]>p[3].

Exemplul 1

inversiuni.in

4
2 1 3 4

inversiuni.out

0

Explicație

Se așează elementele pe masă astfel:

  • 2
  • 1 2 (1 este așezat la stânga)
  • 1 2 3 (3 este așezat la dreapta)
  • 1 2 3 4 (4 este așezat la dreapta)

Se obține permutarea identică, adică zero inversiuni.

Exemplul 2

inversiuni.in

4
2 1 4 3

inversiuni.out

1

Explicație

Se așează elementele pe masă astfel:

  • 2
  • 1 2 (1 este așezat la stânga)
  • 1 2 4 (4 este așezat la dreapta)
  • 1 2 4 3 (3 este așezat la dreapta)

Se obține o permutare care are o inversiune.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Inversiuni:

/*
    Complexitate O(N log N)
*/
#include <fstream>
//#include <iostream>
#define inFile "inversiuni.in"
#define outFile "inversiuni.out"

using namespace std;

int n, a[200005];

inline void Update(int x)
{
    for(int i=x;i<=n;i+=(i&(-i)))
        a[i]++;
}

inline int Query(int x)
{
    int s=0;
    for(int i=x;i>0;i-=(i&(-i)))
        s+=a[i];
    return s;
}

int main()
{
    int i, mari, mici, x;
    long long cnt;
    ifstream fin(inFile);
    fin >> n;
    cnt = 0;
    for (i = 1; i <= n; ++i)
    {
        fin >> x;
        mici = Query(x);
        mari = i - mici - 1;
        //cout << i << " " << mici << " " << mari << "
";
        if (mici < mari) cnt += mici;
        else cnt += mari;
        Update(x);
    }
    fin.close();

    ofstream fout(outFile);
    fout << cnt << "
";
    fout.close();

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1715 Inversiuni

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1715 Inversiuni de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!