歪斜排序

测试数据来自 system/1449

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制:1秒  内存限制:256M


【问题描述】

  农夫约翰有 2N2^N 头奶牛,每头奶牛在身体侧面用油漆写上了一个数字标记,取值范围为 1..2N1..2^N。它们按随机的顺序站在在一条线上。第一头牛是 cow1cow_1,第二头牛是 cow21cowi2Ncow_2(1 ≤ cow_i ≤ 2^N)。当然,cow1cow_1 不太可能油漆标签也是 11

  FJ执行下面的算法来把它们按顺序排列:
  1. 如果有一个以上的牛,然后把奶牛分成两个大小相等的子组。两个子组继续执行该算法。
  2. 递归返回时,比较两个子组的字典序,如果后面的子组字典序小,将两个子组整体交换

  奶牛想知道执行这个 “排序” 程序一共需要走动多少距离。具体来说,根据奶牛的初始位置,请求出:
  1. 所有奶牛的总行驶距离的总和
  2. 奶牛的执行这个'排序'程序后最终的序列。

【输入格式】

  第 11 行:一个整数:NN
  第 2..2N+12..2^N+1 行:第 i+1i+1 行包含一个整数:cowicow_i

【输出格式】

  第 11 行:一个整数,总行驶距离所有的奶牛;
  第 2..2N+12..2^N+1 行:第 i+1i+1 行包含一个整数:位置 ii 站着的牛。

【输入输出样例1】

 Input

3
8
5
2
3
4
7
1
6

 Output

50
1
6
4
7
2
3
5
8

【数据说明】

  对于 100%100\% 的数据,1N101 ≤ N ≤ 10

【来源】

  Mr.he

代码能力专题训练(一)

未参加
状态
已结束
规则
OI
题目
9
开始于
2024-07-01 10:30
结束于
2024-08-12 02:30
持续时间
1000.0 小时
主持人
参赛人数
24