小杨的握手问题

【问题描述】 小杨的班级里共有N名同学，学号从0至N-1。

某节课上，老师安排全班同学进行一次握手游戏，具体规则如下：老师安排了一 个顺序，让全班N名同学依次进入教室。每位同学进入教室时，需要和已经在 教室内且学号小于自己的同学握手。 现在，小杨想知道，整个班级总共会进行多少次握手。 提示：可以考虑使用归并排序进行降序排序，并在此过程中求解。

【输入描述】 输入包含2行。第一行一个整数N，表示同学的个数；第二行N个用单个空格 隔开的整数，依次描述同学们进入教室的顺序，每个整数在0~N-1之间，表示该 同学的学号。 保证每位同学会且只会进入教室一次。

【输出描述】

输出一行一个整数，表示全班握手的总次数。

【样例输入1】 4 2 1 30 【样例输出1】 2 【样例解释1】 2 号同学进入教室，此时教室里没有其他同学。 1 号同学进入教室，此时教室里有2号同学。1号同学的学号小于2号同学，因 此他们之间不需要握手。 3 号同学进入教室，此时教室里有1,2号同学。3号同学的学号比他们都大，因 此3号同学需要分别和另外两位同学握手。 0 号同学进入教室，此时教室里有1,2,3号同学。0号同学的学号比他们都小，因 此0号同学不需要与其他同学握手。 综上所述全班一共握手0+0+2+0=2次

【样例输入2】

6 0 1 2345

【样例输出2】

15

【样例解释2】

全班所有同学之间都会进行握手，因为每位同学来到教室时，都会发现他的学号 是当前教室里最大的，所以他需要和教室里的每位其他同学进行握手。

【数据规模】

对于30%的测试点，保证N≤100。 对于所有测试点，保证2≤N≤3×105。

【题目大意】 全班N名同学依次进入教室。每位同学进入教室时，需要和已经在教室内且学 号小于自己的同学握手，求整个班级总共会进行多少次握手。可以考虑使用归并 排序进行降序排序

【解题思路】

本题主要考察归并排序算法的实现。函数merge(arr,l,r)接受一个数组arr和 两个索引l和r作为参数，表示要排序的数组范围。函数返回一个整数，表示将 数组从索引l到r范围内的元素排序所需的最小交换次数。

首先检查数组长度是否为2，如果是，则不需要进行排序，直接返回0。

然后计算中间索引mid，并将问题分为两个子问题：左半部分和右半部分。 递归调用merge(arr,l, mid)和 merge(arr, mid, r)分别计算左右子问题的最小交 换次数，并将它们相加得到总的交换次数ans。

创建一个空列表_arr，用于存储合并后的有序数组。使用两个指针i和j分别 指向左半部分和右半部分的第一个元素。

通过比较两个指针所指向的元素的大小，将较小的元素添加到_arr中，并更 新相应的指针。

如果右半部分的元素较小，还需要将左半部分剩余的元素全部添加到_arr中， 并更新指针。累加交换次数ans，将右半部分剩余的元素移动到正确的位置。

最后，将_arr中的元素复制回原数组arr的相应位置，并返回总的交换次数 ans。

获取输入的数据n，arr。

输出调用merge(arr，0，n)函数后的返回值

Limitation

1s, 1024KiB for each test case.