打卡信奥刷题（3141）用C++实现信奥题 P7629 [COCI 2011/2012 #1] SORT

P7629 [COCI 2011/2012 #1] SORT

题目描述

考虑如下的排序算法：

reverse-sort(序列 a) 当 (a 未按非递减顺序排列时) 将 a 划分为最少个数的斜率段 对于每一个长度大于 1 的斜率段 反转(该斜率段)

定义slope为a的递减子串，reverse()将翻转一段序列。

给定一个1 ∼ N 1 \sim N1∼N的排列，保证在第一次划分时每个slope的长度都为偶数，求如果使用这种排序算法对给定的排列进行排序，需要调用多少次reverse(slope)。

输入格式

输入的第一行包含一个正整数N NN。

第二行包含N NN个互不相同的的正整数，代表待排序的排列。

输出格式

输出一行一个整数，表示reverse(slope)需要被调用的次数。

输入输出样例 #1

输入 #1

2 2 1

输出 #1

1

输入输出样例 #2

输入 #2

4 4 3 2 1

输出 #2

1

输入输出样例 #3

输入 #3

4 3 1 4 2

输出 #3

3

说明/提示

【数据范围】

对于100 % 100\%100%的数据，2 ≤ N ≤ 10 5 2 \le N \le 10^52≤N≤105。

【说明】

本题分值按 COCI 原题设置，满分140 140140。

题目译自COCI2011-2012 CONTEST #1T5 SORT。

C++实现

#include<cstdio>usingnamespacestd;constintN=100005;intn,a[N],c[N];longlongans;voidswap(int&x,int&y){x^=y;y^=x;x^=y;}//交换两个元素voidreverse(intl,intr){//翻转区间[l,r]内的元素for(inti=l;i<=r&&(i<<1)<l+r;++i)swap(a[i],a[r+l-i]);++ans;//顺便统计答案}intlowbit(intx){returnx&-x;}//下面三行是经典的树状数组voidupdate(inti,intv){for(;i<=n;i+=lowbit(i))c[i]+=v;}intgetsum(inti){intans=0;for(;i;i-=lowbit(i))ans+=c[i];returnans;}intmain(){scanf("%d",&n);intlas=1;scanf("%d",&a[1]);//先将序列按要求翻转一次for(inti=2;i<=n;++i){scanf("%d",&a[i]);if(a[i]>a[i-1]){reverse(las,i-1);las=i;}}reverse(las,n);for(inti=n;i>=1;--i){ans+=getsum(a[i]);update(a[i],1);}printf("%lld\n",ans);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容