JZOJ_7.19C组第二题 休息

本文主要是介绍JZOJ_7.19C组第二题 休息，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一个序列，每次把里面单调递减的序列翻转过来，求翻多少次能翻成单调上升的状态。

思路

我们先模拟第一轮翻转，之后求出这里面的逆序对的个数就好了。证明方法如下：
逆序对还不是很懂。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int a[100001],n,t[100001];
long long ans;
void merge(int 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];
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int l=1,r=1;for(int i=1;i<=n;i++)//模拟第一轮if(i<n&&a[i]>a[i+1]) r++;else{if(l<r){for (l=l;l<r;l++,r--) swap(a[l],a[r]);ans++;}l=r=i+1;}merge(a,1,n);//归并排序求逆序对printf("%lld",ans);
}

这篇关于JZOJ_7.19C组第二题 休息的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---