A48214. 求逆序对问题给定N个数的序列a1,a2,...aN，定义一个数对(ai, aj)为“重要逆序对”的充要条件为i j且ai 2aj。求给定序列中“重要逆序对”的个数。输入第1行：一个数n，表示序列的长度,第2-n+1行，每行一个数，表示序列从前到后的每个数 a1,a2,⋯,ana1,a2,⋯,an。输出第1行：一个数M，表示给定序列的重要的逆序对数目。样例输入5 9 3 5 3 1样例输出6
填空题
困难
知识点
题目描述
求逆序对问题
给定N个数的序列a1,a2,...aN，定义一个数对(ai, aj)为“重要逆序对”的充要条件为i j且ai 2aj。求给定序列中“重要逆序对”的个数。
输入
第1行：一个数n，表示序列的长度,
第2-n+1行，每行一个数，表示序列从前到后的每个数 a1,a2,⋯,ana1,a2,⋯,an。
输出
第1行：一个数M，表示给定序列的重要的逆序对数目。
样例输入
5
9
3
5
3
1
样例输出
6
参考答案
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<float.h>
using namespace std;
int a[200000], n;
long long cnt = 0;
void merge(int a[], int p, int m, int r)
{
vector<double> a1, a2, a3;
for (int i = p; i <= m; i++)
{
a1.push_back(a[i]);
}
for (int i = m + 1; i <= r; i++)
{
a2.push_back(a[i]);
}
a1.push_back(DBL_MAX);
a2.push_back(DBL_MAX);
int i = 0, j = 0, k = 0;
if (a1[m - p] > 2 * a2[0])
{
while (i < m - p + 1 && j < r - m)
{
if (a1[i] > 2 * a2[j])
{
cnt += m - p - i + 1;
j++;
}
else
{
i++;
}
}
}
i = 0, j = 0, k = 0;
while (k + p <= r)
{
if (a1[i] < a2[j])
{
a[p + k] = a1[i];
k++;
i++;
}
else
{
a[p + k] = a2[j];
k++;
j++;
}
}
}
void mergesort(int a[], int p, int r)
{
if (p < r)
{
int m = (p + r) >> 1;
mergesort(a, p, m);
mergesort(a, m + 1, r);
merge(a, p, m, r);
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
mergesort(a, 0, n - 1);
cout << cnt << endl;
}
上一题
下一题