Zbcxcj @ 2019-05-13 08:15:00
跪求各位大佬帮忙看一下我的代码,始终只有前面一半的用例能过,ans已经设成了long long型了还是没用
#include <bits/stdc++.h>
using namespace std;
// 求数组a(lo..hi)的逆序对个数,逆序对横跨中间索引mid
// 假定a(lo..hi)的两半分别都排好了序(这个方法其实是一个归并排序,temp作为临时数组)
long long merge_pairs(int* a, int* temp, int lo, int mid, int hi) {
int i = lo;
int j = mid + 1;
int k = lo;
long long cnt = 0;
while(i <= mid && j <= hi) {
if(a[i] > a[j]) {
temp[k++] = a[j++];
cnt += mid - i + 1; // 左半边中a[i]与i之后的所有元素与a[j]构成逆序对
}
else {
temp[k++] = a[i++];
}
}
while(i <= mid) temp[k++] = a[i++];
while(j <= hi) temp[k++] = a[j++];
for(int i = lo; i <= hi; i++) {
a[i] = temp[i];
}
return cnt;
}
// 求数组a(lo..hi)的逆序对个数,assert(lo <= hi)
long long reversal_pairs_detail(int* a, int* temp, int lo, int hi) {
if(lo == hi) return 0;
long long cnt = 0;
int mid = (lo + hi) / 2;
cnt += reversal_pairs_detail(a, temp, lo, mid);
cnt += reversal_pairs_detail(a, temp, mid+1, hi);
cnt += merge_pairs(a, temp, lo, mid, hi);
return cnt;
}
// 求数组a前n个元素中逆序对个数
int reversal_pairs(int* a, int n) {
if(!n) return 0;
int temp[n+1];
return reversal_pairs_detail(a, temp, 0, n-1);
}
// 快读
inline int read() {
char ch = getchar();
int x = 0, f = 1;
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') x = x*10 + (ch^48), ch = getchar();
return x*f;
}
int main() {
int n; cin >> n;
int a[n+1];
for(int i = 0; i < n; i++) {
a[i] = read();
}
cout << reversal_pairs(a, n) << endl;
return 0;
}
by _xqy_ @ 2019-05-13 11:53:33
直接利用归并排序求逆序对便好了,为什么要加入其他函数???
by Strong_Jelly @ 2019-05-27 21:01:50
全long long