正題

---

大意

一個序列，每次將一個單調下降的區間翻轉，求最少次數將這個序列變成單調上升。

---

解題思路

考慮將O(n2)O(n2)的暴力轉換。
我們先將開始時單調下降的區間翻轉，然后我們會發現只有每個區間的邊界才會需要交換，因為每個區間已經是單調上升的了。但是每次交換又可能會出現新的需要交換的，這就很像冒泡排序。而冒泡排序需要交換的次數就是逆序對的個數。

---

代碼

#include<cstdio> #include<algorithm> long long h[100001],b[100001],n,s,ls,w; void swap(long long &x,long long &y) {long long z=x;x=y;y=z; } void mage(long long low,long long mid,long long hig)//歸并排序求逆序對 {long long p1=low,g=low;long long p2=mid+1;while (g<=hig){if (p1>mid) {b[g]=h[p2]; p2++;}else if (p2>hig) {b[g]=h[p1]; p1++;}else if (h[p1]>h[p2]) {b[g]=h[p1]; p1++; s+=hig-p2+1;}else {b[g]=h[p2]; p2++;}g++;}for (long long i=low;i<=hig;i++) h[i]=b[i]; } void magesort(long long low,long long hig) {if (low<hig){long long mid=(low+hig)/2;magesort(low,mid);magesort(mid+1,hig);mage(low,mid,hig);} } int main() {scanf("%d",&n);for (long long i=1;i<=n;i++){scanf("%d",&h[i]);}ls=1;h[n+1]=2147483647;for (long long i=1;i<=n;i++)//第一次交換{if (h[i+1]>h[i]){w=(ls+i)/2;for (long long j=ls;j<=w;j++)swap(h[j],h[i-j+ls]);if (i-ls!=0) s++;ls=i+1;}}magesort(1,n);printf("%d",s); }

休息！休息一下！

總結

以上是生活随笔為你收集整理的jzoj3462-休息【归并排序,逆序对】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。