Pagini recente » Cod sursa (job #218782) | Cod sursa (job #788901) | Cod sursa (job #3269191) | Cod sursa (job #2611586) | Cod sursa (job #330657)
Cod sursa(job #330657)
#include<fstream>
using namespace std;
int total;
int n;char linie[10001];
int mergeinv(int in,int mij,int sf)
{char l[5001],r[5001];
for(int i=1;i<=(mij-in+1);i++)
l[i]=linie[i+in-1];
for(int j=1;j<=(sf-mij);j++)
r[j]=linie[j+mij];
int k1=1,k2=1,contor=0,numarat=0,pivot=in;
while(k1<=(mij-in+1) && k2<=(sf-mij))
{if(numarat==0 && l[k1]>r[k2]) {contor+=mij-in+1-k1+1;numarat=1;}
if(l[k1]>r[k2]) {linie[pivot]=r[k2];k2++; numarat=0;}
else{linie[pivot]=l[k1];k1++;}
pivot++;
}
if(k1<=(mij-in+1)) while(k1<=(mij-in+1)) {linie[pivot]=l[k1];k1++;pivot++;}
else while(k2<=(sf-mij)) {linie[pivot]=r[k2];k2++;pivot++;}
return contor;
}
int merge(int in,int sf)
{int total=0;
if(in<sf)
{int mij=(in+sf)/2;
total+=merge(in,mij);
total+=merge(mij+1,sf);
total+=mergeinv(in,mij,sf);
}
return total;
}
int main()
{ifstream in("litere.in");
ofstream out("litere.out");
in>>n;
in.getline(linie,10001);
in.getline(linie,10001);
out<<merge(0,n-1);
return 0;
}