Cod sursa(job #1486424)

Utilizator dnprxDan Pracsiu dnprx Data 14 septembrie 2015 20:33:45
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;

int n, nrInv;
char a[10005];

void Citire()
{
    ifstream fin("litere.in");
    fin >> n;
    fin >> (a + 1);
    a[0] = '*';
    fin.close();
}

void Afisare()
{
    ofstream fout ("litere.out");
    fout << nrInv << "\n";
    fout.close();
}

// interclaseaza a[p..m] si a[m+1..q]
// si contorizeaza inversiunile
void Interclasare(int p, int m, int q)
{
    int i, j, k;
    char b[10001];
    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)
{
    char 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;
}