Se dă șirul a₁, a₂, …, a_n care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j].

Cerința

Să se determine numărul inversiunilor permutării.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând permutarea.

Date de ieșire

Programul va afișa pe ecran numărul S, reprezentând numărul inversiunilor permutării.

Restricții și precizări

1 ≤ n ≤ 100.000

Exemplu

Intrare

5
4 2 5 1 3

Ieșire

Explicație

Cele 6 inversiuni sunt date de perechile de indici (1,2), (1,4), (1,5), (2,4), (3,4), (3,5).

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 nrinversiuni:

#include <bits/stdc++.h>
using namespace std;

long long nrInv;
int a[100005], n, b[100005];

void Citire()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
}

void Afisare()
{
    cout << nrInv;
}

void Interclasare(int p, int m, int q)
{
    int i, j, k;
    i = p; j = m + 1; k = 0;
    while (i <= m && j <= q)
        if (a[i] <= a[j]) b[++k] = a[i++];
        else
        {
            nrInv += (m - i + 1);
            b[++k] = a[j++];
        }
    while (i <= m)
        b[++k] = a[i++];
    while (j <= q)
        b[++k] = a[j++];
    j = p;
    for (i = 1; i <= k; i++)
        a[j++] = b[i];
}

void Sch(int i, int j)
{
    int aux;
    if (a[i] > a[j])
    {
        nrInv++;
        aux = a[i];
        a[i] = a[j];
        a[j] = aux;
    }
}

void MergeSort(int p, int q)
{
    int m;
    if (q - p <= 1) Sch(p, q);
    else
    {
        m = (p + q) / 2;
        MergeSort(p, m);
        MergeSort(m + 1, q);
        Interclasare(p, m, q);
    }
}

int main()
{
    Citire();
    MergeSort(1, n);
    Afisare();
    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 #3206 nrinversiuni

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3206 nrinversiuni 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!

Rezolvare completă PbInfo #3206 nrinversiuni