Skip to content

1161: 快排计数

题目

题目描述

输入$1$到$n$ 的一个排列构成一个序列,输出在这个序列上进行快速排序算法需要的比较次数。

本题的快速排序有以下要求:

  1. 每次选择子数组的第一个元素作为pivot
  2. 在根据pivot划分完的左子数组元素的顺序与原数组中的顺序一致。右子数组同理。

比如:数组为 $5, 3, 6, 8, 2, 4,1 , 9, 10, 7$,选择$5$为pivot,划分得到的左子数组$3, 2, 4,1$,右子数组$6,8,9,10,7$。

输入格式

第一行一个整数$n$,

第二行$n$个整数,是$1$到$n$的一个排列

输出格式

一个整数,表示快速排序的比较次数

样例输入

6 3 2 4 1 6 5

样例输出

9

数据范围

对于$40\%$的数据,$n \le 100$,

对于$60\%$的数据,$n\le 10000$,

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!