Pagini recente » Cod sursa (job #3143806) | Cod sursa (job #2375481) | Cod sursa (job #3206788) | Cod sursa (job #412065) | Cod sursa (job #3277266)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
// Funcția care îmbină cele două jumătăți și numără inversiunile
long long mergeAndCount(vector<char>& arr, vector<char>& temp, int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
long long invCount = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
invCount += (mid - i + 1); // Toate elementele rămase în stânga sunt inversiuni
}
}
// Copiem restul elementelor din stânga (dacă există)
while (i <= mid) temp[k++] = arr[i++];
// Copiem restul elementelor din dreapta (dacă există)
while (j <= right) temp[k++] = arr[j++];
// Copiem înapoi elementele sortate în array-ul original
for (i = left; i <= right; i++) arr[i] = temp[i];
return invCount;
}
// Funcția recursivă Merge Sort care sortează și numără inversiunile
long long mergeSortAndCount(vector<char>& arr, vector<char>& temp, int left, int right) {
if (left >= right) return 0;
int mid = (left + right) / 2;
long long invCount = 0;
invCount += mergeSortAndCount(arr, temp, left, mid); // Sortăm și numărăm în stânga
invCount += mergeSortAndCount(arr, temp, mid + 1, right); // Sortăm și numărăm în dreapta
invCount += mergeAndCount(arr, temp, left, mid, right); // Îmbinăm și numărăm inversiunile între jumătăți
return invCount;
}
int main() {
ifstream fin("litere.in");
ofstream fout("litere.out");
int N;
fin >> N;
vector<char> arr(N);
for (int i = 0; i < N; i++) fin >> arr[i];
vector<char> temp(N);
long long result = mergeSortAndCount(arr, temp, 0, N - 1);
fout << result << "\n";
fin.close();
fout.close();
return 0;
}