Description
休息的時候，可以放松放松渾身的肌肉，打掃打掃衛(wèi)生，感覺很舒服。在某一天，某LMZ 開始整理他那書架。已知他的書有n 本，從左到右按順序排列。他想把書從矮到高排好序，而每一本書都有一個獨一無二的高度Hi。他排序的方法是：每一次將所有的書劃分為盡量少的連續(xù)部分，使得每一部分的書的高度都是單調(diào)下降，然后將其中所有不少于2 本書的區(qū)間全部翻轉(zhuǎn)。重復(fù)執(zhí)行以上操作，最后使得書的高度全部單調(diào)上升。可是畢竟是休息時間，LMZ 不想花太多時間在給書排序這種事上面。因此他劃分并翻轉(zhuǎn)完第一次書之后，他想計算，他一共執(zhí)行了多少次翻轉(zhuǎn)操作才能把所有的書排好序。LMZ 驚奇地發(fā)現(xiàn)，第一次排序之前，他第一次劃分出來的所有區(qū)間的長度都是偶數(shù)。

Input
第一行一個正整數(shù)n, 為書的總數(shù)。

接下來一行n個數(shù)，第i個正整數(shù)Hi，為第i 本書的高度。

Output
僅一個整數(shù)，為LMZ 需要做的翻轉(zhuǎn)操作的次數(shù)。

Sample Input
6

5 3 2 1 6 4

Sample Output
3

【樣例解釋】

第一次劃分之后，翻轉(zhuǎn)(5,3,2,1)，（6,4）。之后，書的高度為1 2 3 5 4 6，然后便是翻轉(zhuǎn)（5,4）即可。

Data Constraint
對于10%的數(shù)據(jù)：n<=50
對于40%的數(shù)據(jù)：n<=3000
對于100%的數(shù)據(jù)：1<=n<=100000, 1<=Hi<=n
.
.
.
.
.

分析

找出所有連續(xù)的單調(diào)下降序列，把它們?nèi)糠D(zhuǎn)過來，每翻轉(zhuǎn)一個序列，ans++，做完后，此為第一次交換。
第一次交換后，剩下的就只能兩兩交換，所以只要求逆序?qū)秃昧恕?
.
.
.
.
.

程序：

#include<iostream> #include<algorithm> using namespace std; long long a[100001],b[100001],n,w,t[100001],ans=0;void merge(long long a[],int l,int r) {if(l==r) return;int mid=(l+r)/2;merge(a,l,mid);merge(a,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;}elset[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 check() {for (int i=2;i<=n;i++)if (a[i]<a[i-1]){w=i;return 1;}return 0; }int main() {cin>>n;int tot=1;b[tot]=1;cin>>a[1];for (int i=2;i<=n;i++){cin>>a[i];if (a[i]>a[i-1]){tot++;b[tot]=i;}}tot++;b[tot]=n;for (int i=2;i<=tot;i++){kp(b[i-1],b[i]);ans++;}merge(a,1,n);cout<<ans; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499917.html

總結(jié)

以上是生活随笔為你收集整理的【NOIP2013模拟联考5】休息(rest)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。