A32861. 求逆序对问题给定N个数的序列a1,a2,...aN，定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。输入本题有多个测试点，每个测试点分为两行：第一行为序列中数字的个数N（1 ≤ N ≤ 200000），第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000)，由空格分开。N=0表示输入结束。输出每个测试…
填空题
困难
知识点
题目描述
求逆序对问题
给定N个数的序列a1,a2,...aN，定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。
输入
本题有多个测试点，每个测试点分为两行：第一行为序列中数字的个数N（1 ≤ N ≤ 200000），第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000)，由空格分开。N=0表示输入结束。
输出
每个测试点一行，输出一个整数，为给序列中“重要逆序对”的个数。
样例输入
10
0 9 8 7 6 5 4 3 2 1
0样例输出
16提示
请注意答案范围，如果使用printf输出long long类型，请用%lld
参考答案
#include <iostream>
using namespace std;
long long sum = 0;
void merge(int *s, int *temp, int startIndex, int endIndex, int mid)
{
int i = startIndex, j = mid + 1, k = startIndex;
int pointer = startIndex;
while(i <= mid && j <= endIndex)
{
if(s[i] > s[j])
{
temp[k] = s[j];
while(s[pointer] <= 2 * s[j] && pointer <= mid)
{
pointer ++;
}
if(pointer != mid + 1)
{
sum += mid - pointer + 1;
}
j ++;
}
else
{
temp[k] = s[i];
i ++;
}
k ++;
}
while(i <= mid)
{
temp[k ++] = s[i ++];
}
while(j <= endIndex)
{
temp[k ++] = s[j ++];
}
for(int i = startIndex; i <= endIndex; i ++)
{
s[i] = temp[i];
}
}
void mergeSort(int *s, int *temp, int startIndex, int endIndex)
{
int mid = (startIndex + endIndex) / 2;
if(startIndex < endIndex)
{
mergeSort(s, temp, startIndex, mid);
mergeSort(s, temp, mid + 1, endIndex);
merge(s, temp, startIndex, endIndex, mid);
}
}
int s[200005] = {};
int temp[400010] = {};
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> s[i];
}
mergeSort(s, temp, 0, n - 1);
cout << sum << endl;
return 0;
}
上一题
下一题