【题目大意】

有 n 个学生，假设第 i 个学生进入教师，找出前 1~i-1 个学生，哪些人的学号比自己小，小的需要握手，贡献值加 1。

【考纲知识点】

基本运算、输入输出语句、循环、归并排序的知识。

【解题思路】

按题目要求定义好需要的变量，并实现输入；

输入 n 个整数，每个数字分别和前面的数字进行比较，如果大于，贡献值加 1。

可以用双重循环模拟，找到答案；

因为数据范围是 300000，双重循环会超时。

归并排序可以求逆序对，逆序对是指：i<j,a[i]>a[j]；本题相当于“顺序

对”,i>j,a[i]>a[j]，同样可以用归并排序求得，时间复杂度是 O(Nlogn)。

写归并排序，在排序的过程中，统计数量，求和可得结果。

【参考代码】

#include <iostream>
using namespace std;
int num[300000];
int tmp[300000];
//归并排序
long long merge(int l, int r) {
    if (l + 1 == r)
        return 0;
    int m = (l + r) / 2;
    //先分
    long long res = merge(l, m) + merge(m, r);
    //后合
    for (int i = l, j = m, k = l; k < r; k++) {
        //左边数组中的学号大，直接排
        if (j == r || (i < m && num[i] > num[j])) {
            tmp[k] = num[i];
            i++;
        } else {//否则右边数组中的学号大，产生逆序对
            tmp[k] = num[j];
            j++;
            //计算逆序对数量
            res += m - i;
        }
    }
    //将排好顺序的数据复制回num数组中
    for (int k = l; k < r; k++)
        num[k] = tmp[k];
    return res;
}
int main() {
    int n = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> num[i];
    cout << merge(0, n) << endl;
    return 0;
}