#4223. 小杨的握手问题(23-9C++六级)
小杨的握手问题(23-9C++六级)
小杨的握手问题
【问题描述】 小杨的班级里共有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.