C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

贪心，树状数组

$\color{red}{样例模拟：}$

$每个小朋友的不高兴度与他的交换次数有关，由此计算一下每个小朋友的交换次数即可$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;
typedef long long ll;

int n;
int tr[N], h[N]; 
int sum[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int v) {
    for (int i = x; i < N; i += lowbit(i)) tr[i] += v;
}

int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> h[i], h[i] ++;

    // 求每个数前面有多少个数比它大
    for (int i = 0; i < n; i ++) {
        sum[i] = query(N - 1) - query(h[i]);
        add(h[i], 1);
    }

    // 每个数后面有多少个数比它小
    memset(tr, 0, sizeof tr);
    for (int i = n - 1; i >= 0; i --) {
        sum[i] += query(h[i] - 1);
        add(h[i], 1);
    }

    ll res = 0;
    for (int i = 0; i < n; i ++) res += (ll)sum[i] * (sum[i] + 1) / 2; // 高斯求和公式

    cout << res;

    return 0;
}