程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2299 - Ultra-QuickSort 統計逆序對

POJ 2299 - Ultra-QuickSort 統計逆序對

編輯:C++入門知識

 可以交換相鄰的數,問最少交換幾次後數列變成非降的..     對於每個數若小於左邊的數與左邊的數交換..大於右邊的數與右邊的數交換...如此可以推出所求的答案等價為這個數列的逆序數...     如果暴力查找逆序數是O(n^2)的...對於此題數據.不可接受...     采用分治的思想...在歸並排序的過程中邊排序邊統計逆序數的個數...         Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include<ctime>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#define oo 100000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 500005
using namespace std; 
int n,a[MAXN],temp[MAXN];
ll ans; 
void merge(int s1,int e1,int s2,int e2)
{
      int x,i,j,num=0;
      i=s1,j=s2;
      for (x=s1;x<=e2;x++)
      {
             if (i>e1) temp[x]=a[j++]; 
               else
             if (j>e2) temp[x]=a[i++];
               else
             if (a[i]>a[j])
             {
                   temp[x]=a[j++];
                   ans+=e1-s1+1-num; //從後面段插進來的數插在了多少個前面段數的前面...
             }else temp[x]=a[i++],num++;
      }
      for (i=s1;i<=e2;i++) a[i]=temp[i];
      return;
}
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);
      merge(l,mid,mid+1,r);
      return;
}
int main()
{ 
      int i;
      while (~scanf("%d",&n))
      {
               if (!n) break;
               for (i=1;i<=n;i++) scanf("%d",&a[i]);
               ans=0;
               merge_sort(1,n);
               printf("%I64d\n",ans);
      }
      return 0;
}

 


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved