秋招模拟赛第二十四场|美团|2023.05.13
- Status
- Done
- Rule
- IOI
- Problem
- 4
- Start at
- 2023-6-3 19:00
- End at
- 2023-6-3 21:00
- Duration
- 2 hour(s)
- Host
- Partic.
- 27
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
塔子哥是一位火车车厢调度员。
这一天,一列带有 n 个编号车厢的列车进站了,编号为 1~n 。但是,这些车厢的编号并不是按从左到右递增的顺序,为了后面的工作方便展开,塔子哥想把火车调整成从左到右递增的顺序,即 [1,2,3,……n] ,但他只能进行一种操作:首先他要在火车中任意选择两个车厢取出。然后他将两个车厢中较大的放在火车的最右边,较小的放在火车的最左边。
他可以进行无限次这样的操作,他想知道最少需要多少次才能将火车调整为从左到右递增的顺序。
第一行是数组的长度: n . 第二行有n个数字 pi (i=1,2,3,…,n) 表示从左到右的车厢编号。( 1≤n≤50000,1≤pi≤n )
输出一个整数,表示最少需要操作多少次。
样例输入
7
1 3 5 2 4 6 7
样例输出
3
样例说明
第一步选择5,3,第二步选2,6,第三步选1,7。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.