P7629 [COCI2011-2012#1] SORT--题解

· · 题解

前言

这题的题面太难读懂了，但是读懂了以后就会发现很简单。

题意理解

把 English 翻译成中文就是

给定一个需要排序的数组a[]
while(a不是一个排序好的序列){
    将a划分成多个连续的下降区间
    将所有这些区间(翻转)
}

要求统计翻转操作的次数。

例如：

1 2 6 5 4 3 8 7

划分完以后就是 1 2|6 5 4 3|8 7

每个"|"之间的区间就是下降的，一共有 3 个区间

然后用 3 次翻转操作就变成了 1 2 3 4 5 6 7 8

分析

为什么这样一直进行下去是可以完成排序的？

对于 8 7 6 5 1 2 3 4 ，变成 5 6 7 8 1 2 3 4 ，那么在区间 [1,4] 和区间 [5,8] 就是有序的了，同样可以想到对整个序列这样转之后序列就在一些范围上有序了。

由于题目要求划分后的序列长度必须为偶数，所以在有序区间 [1,4] 内的数就不能划分，否则会划分成 5|6|7|8 、长度不为偶数

这样就会得到这样一个划分 5 6 7|8 1|2 3 4，恰好在两个有序区间的交界处且这个新的划分区间长度为 2

即使是翻转以后 5 6 7 1 8 2 3 4，也由于区间内元素的有序性只能划分为长度为2的新区间 5 6|7 1|8 2|3 4。

继续翻转之后也是这样的 5 6 1 7 2 8 3 4，也只能划分为长度为2的新区间。

这样就等价于只能选择相邻的元素交换了。也就等价去经典的求逆序对问题了。

题解

根据以上的分析可以得到这样的思路：先按照题意分组翻转一次。然后用树状数组或归并排序求逆序对就可以了。

代码：

#include<cstdio>
using namespace std;
const int N=100005;
int n,a[N],c[N];long long ans;
void swap(int& x,int& y){x^=y;y^=x;x^=y;}//交换两个元素
void reverse(int l,int r){//翻转区间[l,r]内的元素
    for(int i=l;i<=r&&(i<<1)<l+r;++i)swap(a[i],a[r+l-i]);
    ++ans;//顺便统计答案
}
int lowbit(int x){return x&-x;}//下面三行是经典的树状数组
void update(int i,int v){for(;i<=n;i+=lowbit(i))c[i]+=v;}
int getsum(int i){int ans=0;for(;i;i-=lowbit(i))ans+=c[i];return ans;}
int main(){
    scanf("%d",&n);
    int las=1;scanf("%d",&a[1]);//先将序列按要求翻转一次
    for(int i=2;i<=n;++i){
        scanf("%d",&a[i]);
        if(a[i]>a[i-1]){
            reverse(las,i-1);
            las=i;
        }
    }reverse(las,n);
    for(int i=n;i>=1;--i){//然后直接树状数组求逆序对正确性就可以保证了
        ans+=getsum(a[i]);
        update(a[i],1);
    }printf("%lld\n",ans);
    return 0;
}//  94ms /  1.37MB /  705B C++98