简答题
偏难
#7524
求逆序对问题(2024-3-5级) 给定N个数的序列a 1 ,a 2 ,...a N ,定义一个数对(a i , a j )为“重要逆序对”的充要条件为 i <…
求逆序对问题(2024-3-5级)
给定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">//参考代码1
#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><pre class="brush:cpp;toolbar:false">//参考代码2
#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);
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++;
}
}
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><p><br/></p>
这道题暂未补解析。