[C++] B3874 [GESP202309 六级] 小杨的握手问题

发表于 分类于

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

1
2
4
2 1 3 0

输出 #1

1
2

输入输出样例 #2

输入 #2

1
2
6
0 1 2 3 4 5

输出 #2

1
15

说明/提示

样例解释 1:

2 号同学进入教室，此时教室里没有其他同学。

1 号同学进入教室，此时教室里有 2 号同学。1 号同学的学号小于 2 号同学，因此他们之间不需要握手。

3 号同学进入教室，此时教室里有 1, 2 号同学。3 号同学的学号比他们都大，因此 3 号同学需要分别和另外两位同学握手。

0 号同学进入教室，此时教室里有 1, 2, 3 号同学。0 号同学的学号比他们都小，因此 0 号同学不需要与其他同学握手。

样例解释2：

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

对于 30% 的测试点，保证 N ≤ 100。

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

题解

如题面，在归并排序基础上加入一点小料就可以了。 具体来说，由于归并排序会不断分块并从左到右处理，因此每次merge时可认为左侧为已经在教室内，右侧为要依序进入教室的同学。

如果忘记了归并怎么写，可以用 std::stable_sort(begin, end, cmp) 自定义 cmp 来只实现小 trick。 不过 std::stable_sort 在数组长度 <= 32 的时候会使用插入排序，所以可能要做一些额外小处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstdint>
using namespace std;

void merge(uint32_t arr[], uint32_t left, uint32_t mid, uint32_t right, uint64_t &ans){
    uint32_t n1 = mid - left + 1,
        n2 = right - mid;

    uint32_t *l = new uint32_t[n1],
        *r = new uint32_t[n2];

    for(uint32_t i=0;i<n1;i++) l[i] = arr[left+i];
    for(uint32_t i=0;i<n2;i++) r[i] = arr[mid+1+i];

    uint32_t i = 0, j = 0, k = left;
    while(i<n1 && j<n2){
        if(l[i]>=r[j]) arr[k++] = l[i++];
        else{
            ans += n1 - i;
            arr[k++] = r[j++];
        }
    }

    while(i<n1) arr[k++] = l[i++];
    while(j<n2) arr[k++] = r[j++];
}

void mergeSort(uint32_t arr[], uint32_t left, uint32_t right, uint64_t &ans){
    if(left < right){
        uint32_t mid = left + (right - left)/2;
        mergeSort(arr, left, mid, ans);
        // cout << "left: ";
        // for(uint32_t i=left;i<=mid;i++) cout << arr[i] << " ";
        // cout << endl;
        mergeSort(arr, mid+1, right, ans);
        // cout << "right: ";
        // for(uint32_t i=mid+1;i<=right;i++) cout << arr[i] << " ";
        // cout << endl;
        merge(arr, left, mid, right, ans);
        // cout << "after: ";
        // for(uint32_t i=left;i<=right;i++) cout << arr[i] << " ";
        // cout << endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    uint32_t n;
    cin >> n;

    uint32_t *arr = new uint32_t[n];
    for(uint32_t i=0;i<n;i++) cin >> arr[i];

    uint64_t s = 0;
    mergeSort(arr, 0, n-1, s);

    cout << s;
    return 0;
}