Pagini recente » Cod sursa (job #2514660) | Cod sursa (job #2094465) | Cod sursa (job #3224826) | Cod sursa (job #676481) | Cod sursa (job #3172726)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("litere.in");
ofstream fout ("litere.out");
char a[10001] , b[10001];
int nr , n;
void Interclasare (int st , int m , int dr)
{
int k = st;
int i = st;
int j = m + 1;
while (i <= m && j <= dr)
if (a[i] > a[j])
{
b[k++] = a[j++];
nr += (m - i + 1);
}
else b[k++] = a[i++];
while (i <= m) b[k++] = a[i++];
while (j <= dr) b[k++] = a[j++];
for (i = st; i <= dr; i++)
a[i] = b[i];
}
void MergeSort (int st , int dr)
{
int m = (st + dr) / 2;
if (dr - st >= 1)
{
MergeSort (st , m);
MergeSort (m + 1 , dr);
Interclasare (st , m , dr);
}
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i];
MergeSort (1 , n);
fout << nr;
return 0;
}