Pagini recente » Cod sursa (job #1395936) | Cod sursa (job #877025) | Cod sursa (job #2744640) | Cod sursa (job #1293130) | Cod sursa (job #2342844)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
char a[10005], b[10005];
int n, cnt;
ifstream fin("litere.in");
ofstream fout("litere.out");
int Int(int st, int m, int dr)
{
int i, j, k;
i = st; j = m + 1; k = 0;
while(i <= m && j <= dr)
if(a[i] <= a[j])b[++k] = a[i++];
else
{
cnt += (m - i + 1);
b[++k] = a[j++];
}
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 MSort(int st, int dr)
{
if(dr - st <= 1)
{
if(a[st] > a[dr])
{
cnt++;
swap(a[st], a[dr]);
}
}
else
{
int m = (st + dr) / 2;
MSort(st, m);
MSort(m + 1, dr);
Int(st, m, dr);
}
}
int main()
{
fin >> n;
fin.getline(a+1,10005);
MSort(1, n);
fout << cnt << "\n";
return 0;
}