简答题
偏难
#7095
求逆序对问题 给定N个数的序列a 1 ,a 2 ,...a N ,定义一个数对(a i , a j )为“重要逆序对”的充要条件为 i < j 且 a i >…
求逆序对问题
给定N个数的序列a1,a2,...aN,定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。
时间限制:1000
内存限制:256000
输入
本题有多个测试点,每个测试点分为两行:第一行为序列中数字的个数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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
using namespace std;
int arr[200005];
int tmp[200005];
int N;
long long mergesort(int start, int end) {
long long cnt = 0, mid = (start + end) / 2;
if (start >= end)
return 0;
cnt += mergesort(start, mid);
cnt += mergesort(mid + 1, end);
// find important reverse pair
int i = start, j = mid + 1;
while (i <= mid && j <= end) {
if (arr[i] > 2 * arr[j] && j <= end) {
cnt += (mid - i + 1);
j++;
} else {
i++;
}
}
// merge sort
i = start, j = mid + 1;
int idx = 0;
while (i <= mid && j <= end) {
if (arr[i] > arr[j]) {
tmp[idx++] = arr[j++];
} else {
tmp[idx++] = arr[i++];
}
}
while (i <= mid)
tmp[idx++] = arr[i++];
while (j <= end)
tmp[idx++] = arr[j++];
for (int k = 0; k < idx; k++) {
arr[start + k] = tmp[k];
}
return cnt;
}
int main() {
while (cin >> N) {
if (N == 0)
break;
for (int i = 1; i <= N; i++) {
cin >> arr[i];
}
cout << mergesort(1, N) << endl;
}
return 0;
}</pre>
这道题暂未补解析。