GESP认证C++编程真题解析 | B3874 [GESP202309 六级] 小杨的握手问题

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[B3874 GESP202309 六级] 小杨的握手问题 - 洛谷

【题目描述】

小杨的班级里共有N NN名同学，学号从0 00至N − 1 N-1N−1。

某节课上，老师安排全班同学进行一次握手游戏，具体规则如下：老师安排了一个顺序，让全班N NN名同学依次进入教室。每位同学进入教室时，需要和已经在教室内且学号小于自己的同学握手。

现在，小杨想知道，整个班级总共会进行多少次握手。

提示：可以考虑使用归并排序进行降序排序，并在此过程中求解。

【输入】

输入包含2 22行。第一行一个整数N NN，表示同学的个数；第二行N NN个用单个空格隔开的整数，依次描述同学们进入教室的顺序，每个整数在0 ∼ N − 1 0 \sim N-10∼N−1之间，表示该同学的学号。

保证每位同学会且只会进入教室一次。

【输出】

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

【输入样例】

4 2 1 3 0

【输出样例】

2

【算法标签】

《洛谷 B3874 小杨的握手问题》 #树状数组# #递归# #排序# #GESP# #2023#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=300005;// 树状数组大小，要大于最大可能的值intn;// 数组长度intans;// 逆序对总数inttr[N];// 树状数组/** * 计算lowbit：返回x的二进制表示中最低位的1所对应的值 * 例如：lowbit(6)=2，因为6的二进制是110，最低位的1表示2 * @param x 输入数字 * @return lowbit值 */intlowbit(intx){returnx&-x;// 利用补码性质：x & -x}/** * 树状数组更新操作 * 在位置x上增加c * @param x 更新位置 * @param c 增加的值 */voidadd(intx,intc){// 从x开始，沿lowbit路径向上更新所有包含x的区间for(inti=x;i<=N;i+=lowbit(i)){tr[i]+=c;}}/** * 树状数组查询操作 * 查询前缀和[1, x] * @param x 查询位置 * @return 前缀和 */intquery(intx){intres=0;// 从x开始，沿lowbit路径向下累加for(inti=x;i;i-=lowbit(i)){res+=tr[i];}returnres;}signedmain()// 因为使用了#define int long long{// 输入数组长度cin>>n;// 从后向前遍历数组for(inti=n;i>=1;i--){intx;cin>>x;x++;// 将数值从0-based转为1-based，避免树状数组处理0// 查询在当前位置之前（在原始顺序中）有多少个比x小的数// 因为是从后向前遍历，所以query(x)返回的是已经处理过的数中小于等于x的数量// 但我们需要的是严格小于x的数量，所以这里有问题ans+=query(x);// 将当前数加入树状数组add(x,1);}// 输出逆序对总数cout<<ans<<endl;return0;}

【运行结果】

4 2 1 3 0 2