歪斜排序
测试数据来自 system/1449
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
时间限制:1秒 内存限制:256M
【问题描述】
农夫约翰有 头奶牛,每头奶牛在身体侧面用油漆写上了一个数字标记,取值范围为 。它们按随机的顺序站在在一条线上。第一头牛是 ,第二头牛是 。当然, 不太可能油漆标签也是 。
FJ执行下面的算法来把它们按顺序排列:
1. 如果有一个以上的牛,然后把奶牛分成两个大小相等的子组。两个子组继续执行该算法。
2. 递归返回时,比较两个子组的字典序,如果后面的子组字典序小,将两个子组整体交换
奶牛想知道执行这个 “排序” 程序一共需要走动多少距离。具体来说,根据奶牛的初始位置,请求出:
1. 所有奶牛的总行驶距离的总和
2. 奶牛的执行这个'排序'程序后最终的序列。
【输入格式】
第 行:一个整数:;
第 行:第 行包含一个整数:。
【输出格式】
第 行:一个整数,总行驶距离所有的奶牛;
第 行:第 行包含一个整数:位置 站着的牛。
【输入输出样例1】
Input
Output
【数据说明】
对于 的数据,
【来源】
Mr.he