2014年第五届蓝桥杯省赛-J. 小朋友排队

原题链接

题面

n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是 0。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加 1，如果第二次要求他交换，则他的不高兴程度增加 2（即不高兴程度为 3），依次类推。当要求某个小朋友第 k 次交换时，他的不高兴程度增加 k。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

输入描述

输入描述

输入的第一行包含一个整数 n，表示小朋友的个数。

第二行包含 n 个整数 $H_1 H_2 ... H_n$，分别表示每个小朋友的身高。

其中，$1 \leq n \leq 10^5$，$0 \leq H_i \leq 10^6$。

输出描述

输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

输入样例

3
3 2 1

输出样例

9

题解

树状数组，排序

由题，若一个小朋友左边有比他高的，那这两个小朋友肯定需要经过一次交换。同理，若其右边有比他矮的，那这两人也需要经过一次交换，最终才能得到非降序的排列。

则，直接统计每个小朋友前面身高严格大于其的数量+右边严格小于其的数量，这个和（记为b[i]）代表该小朋友的需经过交换次数，则其不高兴程度为 $\frac{b[i]\times (b[i] + 1)}{2}$，再累加每个小朋友的不高兴程度即可。

由上分析，用前缀和 s[x] 表示身高小于等于 x 的人数，执行以下流程：

• 从前往后遍历身高，则比小朋友 i 的身高 a[i] 高的人数为 s[m] - s[a[i]] （m为所有小朋友的最高身高），将其存入 b[i] （需经过的交换次数）。同时，再将当前身高a[i] 的人数加1，并更新 s[a[i]...m] 的值，之后进入下一次循环。
• 重置前缀和数组s 为0，从后往前遍历身高，则比小朋友 i 的身高 a[i] 低的人数为 s[a[i] - 1] ，将其加入 b[i] （需经过的交换次数和）。同时，再将当前身高a[i] 的人数加1，并更新 s[a[i]...m] 的值，之后进入下一次循环。

如上，则两个方向的遍历就可以统计出每个小朋友需要交换的次数，最后再将次数转换为不高兴程度求和即为最终答案。

但需注意，若用简单的数组来维护前缀和操作，每次循环需更新前缀和数组 $O(m)$ 次，则复杂度为 $O(nm)$ ，最坏情况下的运算数量级为 $10^{11}$ ，会超时。所以，这里借助数据结构 树状数组 来维护前缀和，其每次查找和更新的前缀和的复杂度为 $O(\log_2^m)$ ，总的时间复杂度为 $O(n\log_2^m)$，最坏情况下运算数量级为 $10^6$ 。

注意： 此题最坏情况下可能有小朋友会交换 $10^5 - 1$ 次，转变为不高兴程度为 $5\times(10^9 - 10^4)$，会爆int，需要开long long来存答案。

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e5 + 5, M = 1e6 + 5;
int n, m;
int a[N], c[M], b[N];

void add(int x, int v) {
    for (; x <= m; x += x & -x) c[x] += v;
}

int get(int x) {
    int s = 0;
    for (; x; x -= x & -x) s += c[x];
    return s;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[i]++;
        m = max(a[i], m);
    }

    //前往后扫，统计前面比小朋友身高高的人数
    for (int i = 1; i <= n; i++) {
        b[i] += get(m) - get(a[i]);
        add(a[i], 1);
    }

    //后往前扫，统计后面比小朋友身高低的人数
    memset(c, 0, sizeof c);
    for (int i = n; i; i--) {
        b[i] += get(a[i] - 1);
        add(a[i], 1);
    }

    LL ans = 0;
    for (int i = 1; i <= n; i++) ans += b[i] * 1ll * (b[i] + 1) / 2;
    cout << ans << endl;

    return 0;
}