Pagini recente » Cod sursa (job #780652) | Cod sursa (job #2533971) | Cod sursa (job #2039500) | Cod sursa (job #1328201) | Cod sursa (job #1486424)
#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;
}