Pagini recente » Cod sursa (job #1961206) | Cod sursa (job #1372519) | Cod sursa (job #685863) | Cod sursa (job #1485677) | Cod sursa (job #1785683)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("litere.in");
ofstream fout("litere.out");
int n,a[10005],b[10005];
char cuv[10005];
long long cnt;
void Citire()
{
int i;
fin>>n;
fin>>cuv;
for(i=0;i<n;i++)
a[i+1]=(cuv[i]-'a')+1;
}
void Interclasare(int st,int m,int dr)
{
int i,j,k;
i=st;
j=m+1;
k=0;
while(i<=m and 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=1;i<=k;i++)
a[st++]=b[i];
}
void Mergesort(int st,int dr)
{
int m;
if(dr-st<=1)
{
if(a[st]>a[dr])
{
cnt++;
swap(a[st],a[dr]);
}
}
else
{
m=(st+dr)/2;
Mergesort(st,m);
Mergesort(m+1,dr);
Interclasare(st,m,dr);
}
}
int main()
{
Citire();
Mergesort(1,n);
fout<<cnt<<"\n";
fin.close();
fout.close();
return 0;
}