「NOIP模拟赛」翻转排序
题目描述
Alex得到了存放着一个1-n排列的容器。这个容器支持的唯一操作,是翻转排列的某一段。思考很久之后,他决定用以下方式让这个排列有序:
1 找到每一个极大的下降子序列(子序列要求连续)
2 对于每个长度大于1的极大下降子序列,对它进行翻转
3 如果排列依然不是有序的,转1
我们举一个例子:初始排列是(5 3 1 4 2)
一开始极大的下降子序列是(5 3 1)(4 2)
把这些序列翻转后得到1 3 5 2 4
接下来的极大下降子序列是(1)(3)(5 2)(4)
翻转后是1 3 2 5 4
接下来的极大下降子序列是(1)(3 2)(5 4)
翻转后是1 2 3 4 5,满足要求
定义翻转一个子序列的费用为1(注意一轮翻转的费用可能大于1),那么上面的费用一共是2+1+2=5。
现在,给你一个排列,你要求出对这个排列排序的费用。
另外题目保证:第一次划分时,所有极大下降子序列的长度都是偶数
输入
第一行一个整数N
第二行表示N个数的排列
输出
所需费用。如果不能排序,输出-1
样例输入
4
3 1 4 2
样例输出
3
数据范围
对于10%的数据,N<=10
对于40%的数据,N<=3000
对于100%的数据,N<=100000
题解
我的想法比较奇怪
如果每次只能翻转俩个,那么显然是求逆序对
而这题每次可以翻转一个递减的序列,如果它的长度为l
则我们多翻转了(l+1)*l/2-1
于是我们再扫一遍将答案减去每一段递减序列的(l+1)*l/2-1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<iostream> #include<cstring> #include<cstdio> #define inf 0x7fffffff using namespace std; int n,a[100001],temp[100001]; long long sum; void sort(int l,int r) { int i,j,k; if(l<r) { k=0; int mid=(r+l)>>1; sort(l,mid);sort(mid+1,r); for(i=l,j=mid+1;i<=mid&&j<=r;) { if(a[i]>a[j])temp[k++]=a[j++]; else { sum+=j-mid-1; temp[k++]=a[i++]; } } while(i<=mid) { sum+=j-mid-1; temp[k++]=a[i++]; } while(j<=r)temp[k++]=a[j++]; j=l; for(i=0;i<k;i++)a[j++]=temp[i]; } } int main() { //freopen("sort.in","r",stdin); //freopen("sort.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); int t=a[1],tot=1; for(int i=2;i<=n;i++) { if(a[i]<t)tot++; else {sum-=(tot*(tot-1)/2-1);tot=1;} t=a[i]; } sum-=(tot*(tot-1)/2-1); sort(1,n); printf("%I64d",sum); return 0; } |
Subscribe