Pagini recente » Cod sursa (job #2469533) | Cod sursa (job #1531328) | Cod sursa (job #100501) | Cod sursa (job #2178507) | Cod sursa (job #3172709)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("litere.in");
ofstream fout("litere.out");
int a[10003], b[10003], n, cnt;
void Intercl(int st, int m, int dr)
{
int i, j, k;
k = i = st;
j = m + 1;
while (i <= m && j <= dr)
if (a[i] <= a[j]) b[k++] = a[i++];
else
{
b[k++] = a[j++];
cnt += m - i + 1;
}
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 Msort(int st, int dr)
{
if (dr - st >= 1)
{
int m = (st + dr) / 2;
Msort(st, m);
Msort(m + 1, dr);
Intercl(st, m, dr);
}
}
int main()
{
int i;
char x;
fin >> n;
for (i = 1; i <= n; i++)
{
fin >> x;
a[i] = x;
}
Msort(1,n);
fout << cnt;
return 0;
}