Для данной постановки задачи нам нужно вычислить количество инверсий в массиве, поэтому я попытался применить алгоритм, использующий сортировку слиянием и вычисляющий количество инверсий при объединении, а также во время сортировки. В то время как мой код дает тот же ответ для тестовых случаев, которые я подал в систему, что и мои собственные решения, я получаю неправильный ответ от онлайн-судьи — Codechef. Пожалуйста, скажи мне мою ошибку.
ссылка на проблему: http://www.codechef.com/COOK43/problems/LPAIR
код:
#include<iostream>
using namespace std;
long long int Merge(int* left,int* right,int* arr,int nl,int nr)
{
int i=0;
int j=0;
int k=0;
long long int cnt=0;
while(i<nl&&j<nr)
{
if(left[i]<=right[j])
{
arr[k]=left[i];
i++;
}
else
{
arr[k]=right[j];
j++;
cnt+=nl-i;
}
k++;
}
while(i<nl)
{
arr[k]=left[i];
i++;
k++;
}
while(j<nr)
{
arr[k]=right[j];
j++;
k++;
}
return cnt;
}
long long int MergeSort(int *a,int len)
{
long long int cnt=0;
if(len<2)
return 0;
int mid=len/2;
int* left=new int[mid];
int* right=new int[len-mid];
for(int i=0;i<mid;i++)
left[i]=a[i];
for(int i=mid;i<len;i++)
right[i-mid]=a[i];
cnt+=MergeSort(left,mid);
cnt+=MergeSort(right,len-mid);
cnt+=Merge(left,right,a,mid,len-mid);
delete(left);
delete(right);
return cnt;
}
int main()
{
int n;
cin>>n;
int* fm=new int[n];
for(int i=0;i<n;i++)
cin>>fm[i]>>fm[i];
cout<<MergeSort(fm,n);
}
Это правильный подход и у вас очень простая проблема — количество инверсий для n = 105 может переполнить целое число. Подумайте, как вы можете это исправить.
Ошибка в том, что входные пары мужчин и женщин не будут даны как отсортированные по мужской шеф-повару Ми.
Перед запуском сортировки слиянием необходимо отсортировать пару на основе Mi < Мужской номер> потому что мужчина должен стоять в возрастающем порядке.
поэтому ваш массив fm должен быть массивом пар, а затем отсортировать его по Mi.
И тогда вся операция в сортировке слиянием будет основана на втором элементе fm (fm.second)