[jzoj 3462] 【NOIP2013模擬聯考5】休息 {歸併排序(逆序對) 快速排序}

NO IMAGE

題目

Description
休息的時候,可以放鬆放鬆渾身的肌肉,打掃打掃衛生,感覺很舒服。在某一天,某LMZ 開始整理他那書架。已知他的書有n 本,從左到右按順序排列。他想把書從矮到高排好序,而每一本書都有一個獨一無二的高度Hi。他排序的方法是:每一次將所有的書劃分為儘量少的連續部分,使得每一部分的書的高度都是單調下降,然後將其中所有不少於2 本書的區間全部翻轉。重複執行以上操作,最後使得書的高度全部單調上升。可是畢竟是休息時間,LMZ 不想花太多時間在給書排序這種事上面。因此他劃分並翻轉完第一次書之後,他想計算,他一共執行了多少次翻轉操作才能把所有的書排好序。LMZ 驚奇地發現,第一次排序之前,他第一次劃分出來的所有區間的長度都是偶數。
Input
第一行一個正整數n, 為書的總數。
接下來一行n個數,第i個正整數Hi,為第i 本書的高度。
Output
僅一個整數,為LMZ 需要做的翻轉操作的次數。


解題思路

10%演算法:呵呵,對於這種神奇的演算法還是表示不明覺厲。
100%演算法:一個並不明顯的性質是,在對原序列進行第一次劃分過後,以後
的每次劃分得到的各個部分都恰好由兩個陣列成。 這是因為在第一次劃分和
第一輪的翻轉之後,原數列由若干個單調增序列拼接而成,形式如下:a1,a2…ai,b1,b2…bj…z1…zk.” role=”presentation”>a1,a2…ai,b1,b2…bj…z1…zk.a1,a2…ai,b1,b2…bj…z1…zk.a1, a2…ai, b1, b2…bj…z1…zk.考慮相鄰兩個部分,不妨設為 a 部分和 b 部分,其中 ai和 b1前後相鄰。若 ai&lt;b1″ role=”presentation”>ai<b1ai<b1ai<b1則可以合併成同一部分,否則會形成塊(ai,b1)” role=”presentation”>(ai,b1)(ai,b1)(ai, b1),並且在下一輪翻轉,成為…ai−1,b1,ai,b2…” role=”presentation”>…ai−1,b1,ai,b2……ai−1,b1,ai,b2……ai-1, b1, ai, b2…。可以發現在這以後,由於有 ai−1&lt;ai” role=”presentation”>ai−1<aiai−1<aiai-1<ai,則 ai−1″ role=”presentation”>ai−1ai−1ai-1與 ai” role=”presentation”>aiaiai不會在同一個塊裡;同理 b1″ role=”presentation”>b1b1b1和 b2″ role=”presentation”>b2b2b2不會在同一個塊裡。即,任意連續三個數必定不會是單調遞減的。 那麼,這以後每次翻轉都只會將相鄰的逆序對交換。由於這個演算法最終可以正確地得到結果,所以第一輪以後進行的翻轉運算元就等於第一輪之後序列的逆序對數。而第一輪的翻轉數我們可以直接模擬得到。 求一個序列的逆序對數的經典做法是歸併排序,同時記錄。時間複雜度 O(nlog2n)” role=”presentation”>O(nlog2n)O(nlog2n)O(nlog2n)


程式碼

#include<cstdio>
#include<algorithm>
using namespace std;
int t[400005],n,a[400005],tot,b[400005]; long long ans; 
void merge(int l,int r){
if(l==r) return;
int mid=(l r)>>1;
merge(l,mid);  merge(mid 1,r);
int i=l,j=mid 1,p=l;
while(i<=mid&&j<=r)
{
if(a[i]>a[j])
{
t[p  ]=a[j  ];
ans =mid-i 1;
}
else t[p  ]=a[i  ];
}
while(i<=mid)  t[p  ]=a[i  ];
while(j<=r)   t[p  ]=a[j  ];
for(i=l;i<=r;i  )
a[i]=t[i];
}
void kp(int l,int r)
{
if (l>=r) return;
int i=l,j=r,mid=a[(l r)/2];
do
{
while (a[i]<mid) i  ;
while (a[j]>mid) j--;
if (i<=j)
{
swap(a[i],a[j]);
i  ; j--;
}
}while (i<=j);
}
int main(){
scanf("%d",&n);
scanf("%d",&a[1]); b[  tot]=1; 
for(int i=2;i<=n;i  ) 
{
scanf("%d",&a[i]);
if (a[i]>a[i-1]) b[  tot]=i; 
} 
b[  tot]=n; 
for (int i=2;i<=tot;i  )
kp(b[i-1],b[i]),ans  ; 
merge(1,n);
printf("%lld",ans); 
}