根据贪心及逆序对的知识
难点是推算出每个小朋友移动的次数是k1+k2是固定的
k1为小于这个小朋友高度的个数 k2为大于这个小朋友高度的个数
利用树状数组快速求和
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
//h数组存储身高
//tre数组为树状数组
int h[N], tre[N];
//sum数组存储每个小朋友的不高兴度
int sum[N];
int n;
typedef long long LL;
int lowbit(int x) {
return x & (-x);
}
void add(int x, int y) {
for (int i = x; i < N; i+=lowbit(i)) {
tre[i] += y;
}
}
LL query(int x) {
LL res = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
res += tre[i];
}
return res;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) {
cin >> h[i];
//身高是从0开始,所以++ 从1开始
h[i]++;
}
//找出比这个数大的数有多少个
for (int i = 0; i < n; i++) {
sum[i] += query(N - 1)-query(h[i]);
add(h[i], 1);
}
//清空树状数组
memset(tre, 0, sizeof(tre));
//找出比这个数小的数有多少个
//注意这里必须倒着更新,否则无法算出高的层的数值
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++) {
//等差数列求和 不高兴度的总和为从1+2+..+sum[i]
res += (LL)sum[i] * (sum[i] + 1) / 2;
}
cout << res << endl;
return 0;
}