Pagini recente » Borderou de evaluare (job #1392630) | Cod sursa (job #2185671) | Borderou de evaluare (job #3001808) | Cod sursa (job #2768460)
#include <fstream>
#include <iostream>
using namespace std;
int n;
int a[10001];
void read() {
int i;
char ch;
ifstream f("litere.in");
f >> n;
for (i = 1; i <= n; i++) {
f >> ch;
a[i] = ch - 'a';
}
f.close();
}
int nr;
int aux[10001];
void merge_sort(int st, int dr) {
if (st == dr)
return;
else {
int mij = (st + dr) / 2;
merge_sort(st, mij);
merge_sort(mij + 1, dr);
int i, j, k = 0;
i = st, j = mij + 1;
while (i <= mij && j <= dr) {
if (a[i] <= a[j])
aux[++k] = a[i++];
else {
nr += (j - (k + st));
aux[++k] = a[j++];
}
}
while (i <= mij)
aux[++k] = a[i++];
while (j <= dr)
aux[++k] = a[j++];
for (k = 0, i = st; i <= dr; i++)
a[i] = aux[++k];
}
}
void output() {
ofstream g("litere.out");
g << nr;
g.close();
}
int main() {
read();
int i;
merge_sort(1, n);
output();
return 0;
}