输入

第1行：N，N为序列的长度（n <= 50000)第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）

输出

输出逆序数

输入样例

输出样例

4 试了一下，这道题应该给的是互不相同的n个数。 归并排序合并过程来完成。 代码：

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #define MAX 50000#define DMAX 10000using namespace std;int n,ar[MAX],ans;void merge_sort(int l,int r) { if(l == r) return; int mid = (l + r) / 2; merge_sort(l,mid); merge_sort(mid + 1,r); int *p = new int[r - l + 1]; int a = l,b = mid + 1,i = 0; while(a <= mid || b <= r) { if(b > r || a <= mid && ar[a] < ar[b]) { p[i ++] = ar[a ++]; } else { p[i ++] = ar[b ++]; ans += mid - a + 1; } } for(int i = l;i <= r;i ++) { ar[i] = p[i - l]; } } int main() { scanf("%d",&n); for(int i = 0;i < n;i ++) { scanf("%d",&ar[i]); } merge_sort(0,n - 1); printf("%d",ans); }

也可以用树状数组来实现。因为数很大，数组下标不能装，但是总的n个数，数组下标还是可以装的，所以把数用map映射到1-n，排好序之后，按照映射的下标排着找逆序数，注意这个时候的逆序数实际上是原来未排序时原来序列的正序数，所以用(n - 1) * n / 2减去就是答案。也可以存一下原序列，排序后再映射，然后按照原序列插入树状数组来计算。

代码：

#include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #define MAX 50000#define DMAX 10000using namespace std;typedef long long ll; int n,ar[MAX]; ll ans; int sum[MAX + 1]; map
            
              mp; int lowbit(int t) {return t&-t;} void update(int x) { while(x <= n) { sum[x] ++; x += lowbit(x); } } int getsum(int x) { int c = 0; while(x > 0) { c += sum[x]; x -= lowbit(x); } return c; } int main() { scanf("%d",&n); ans = (ll)(n - 1) * n / 2; for(int i = 0;i < n;i ++) { scanf("%d",&ar[i]); mp[ar[i]] = i + 1; } sort(ar,ar + n); for(int i = 0;i < n;i ++) { ans -= getsum(mp[ar[i]] - 1); update(mp[ar[i]]); } printf("%lld",ans); }

转载于:https://www.cnblogs.com/8023spz/p/10072873.html

你可能感兴趣的文章