塔子哥住的宿舍有一台电梯。大家有一个约定俗成的规矩:如果你要去的楼层的相邻楼层已经在之前被按下,则你不允许再按下按钮,等出电梯再自行上/下一层!
每个人都有一个想去的楼层xi,这构成一个排队序列S.不同的入电梯顺序可能会导致不同的电梯按钮状态。例如:
S=[1,2,3] , 那么电梯按钮状态为:{1,3}
S=[2,3,1] , 那么电梯按钮状态为:{2}
从左至右为先后入电梯的顺序。
进一步讲,对于一种排队序列S , 我们有一个冗余值p(S) , 它描述的是最终大家需要爬楼的层数之和。例如:
S=[1,2,3] , 那么 p(S)=1 , 因为第2个人需要爬一层。
S=[2,3,1] , 那么 p(S)=2 , 因为第1,3个人都需要爬一层。
塔子哥是个圣母,他不是希望自己不需要爬楼,而是希望大家爬楼的总和尽量小(即最小化冗余值)。你能告诉他一种合理的排队序列,使得得到最小的冗余值是多少吗?
第一行输入一个整数n , 代表集合大小
第二行输入n个整数si, 代表每个人要去的楼层。
输出一行代表集合的所有排列的效度之和。
n | si | 占比 |
---|---|---|
≤20 | [1,n] | 20% |
≤1000 | [1,n] | 50% |
≤100000 | 80% | |
[1,1e9] | 100% |
输入
3
1 2 3
输出
1
样例说明
让他们排成[1,3,2] 或者[3,1,2] 即可得到最小冗余值, 需要移动的人是要去第2楼的人,,所以冗余值是2
输入
6
1 2 2 2 2 3
输出
2
让他们排成[2,2,2,2,1,3] 即可得到最小冗余值 , 需要移动的人是要去第1,3楼的人,所以冗余值是2
本题属于以下题库,请选择所需题库进行购买