Pagini recente » Cod sursa (job #1198083) | Cod sursa (job #849934) | Cod sursa (job #1689903) | Cod sursa (job #1987755) | Cod sursa (job #2669647)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("litere.in");
ofstream fout("litere.out");
char a[10003], b[10003];
int n, k, nrschimb;
void Citire()
{
int i;
fin >> n;
for(i = 1;i <= n;i++)
fin >> a[i];
}
void Merge(int st, int m, int dr)
{
int i, j;
k = 0;
i = st; j = m + 1;
while(i <= m && j <= dr)
{
if(a[i] > a[j])
{
b[++k] = a[j++];
nrschimb += m - i + 1;
}
else
b[++k] = a[i++];
}
while(i <= m) b[++k] = a[i++];
while(j <= dr) b[++k] = a[j++];
j = 1;
for(i = st;i <= dr;i++)
a[i] = b[j++];
}
void Sch(int p, int q)
{
if(a[p] > a[q])
{
swap(a[p],a[q]);
nrschimb++;
}
}
void DI(int st, int dr)
{
if(dr - st <= 1)
Sch(st, dr);
else
{
int mij = (st + dr) / 2;
DI(st, mij);
DI(mij + 1, dr);
Merge(st, mij, dr);
}
}
int main()
{
Citire();
DI(1, n);
fout << nrschimb;
fin.close();
fout.close();
return 0;
}