AcWing 1215. 小朋友排队 （树状数组）

本文主要是介绍AcWing 1215. 小朋友排队 （树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$n$ 个小朋友站成一排。

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

每个小朋友都有一个不高兴的程度。

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

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

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

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

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

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

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

数据范围
$1\le n\le 100000,$
$0\le H_i\le 1000000$
输入样例：

3
3 2 1

输出样例：

9

样例解释
首先交换身高为 $3$ 和 $2$ 的小朋友，再交换身高为 $3$ 和 $1$ 的小朋友，再交换身高为 $2$ 和 $1$ 的小朋友，每个小朋友的不高兴程度都是 $3$，总和为 $9$ 。

---

首先明确只能相邻的人之间换，而且每次换的时候，比如 $1$ 和 $2$ 换，那么他们两个人的不高兴都会加上他们各自交换过的次数。

对于样例我们只看中间的 2，2 的左边有一个 3，这个 3 应该在 2 的右边，2 的右边有一个 1，这个 1 应该在 2 的左边，不管怎么换 2 都会被换两次，因为如果 2 先和 3 换，3 和 1 换，1 和 2 换， 2 换了两次，如果 2 先和 1 换， 3 和 1 换，3 和 2 换，2 还是换了两次。

对于 1 也是，因为左边有两个比他大的，所以 1 要换两次。

对于任何一个数，如果左边有比他大的，就一定要跨过他去，如果右边有比他小的，也一定要跨过他去，这么下来就交换了左边比他大的个数加右边比他小的个数的次数，这样得来的就已经是最小的交换次数了，因为不可能比这个小的情况，如果有就不满足升序了。

那么我们就需要实现求出来某个数左边比他大的数的个数和右边比他小的数的个数。可以有很多方法，这里使用树状数组实现。

这里树状数组代表的是某个数有没有，如果有就是 1，没有就是 0 。
之后如果要求a[i]的左边比它大的数，只要求从左边扫过去，然后求出最大高度的前缀和减去a[i]的前缀和
求右边的比当前数小的数则是从右边扫，其他的同理。

此种做法是树状数组的一种管用用法，可以参考树状数组的笔记

代码：

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;int tr[M];
int a[N];
int n;
int times[N];	//存每个数的交换个数int lowbit(int x) { return x & -x; }
void add(int x, int c) {for (int i = x; i <= M; i+=lowbit(i))tr[i] += c;
}
int sum(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 = 1; i <= n; i++) {cin >> a[i];a[i] ++;}for (int i = 1; i <= n; i++) {times[i] = sum(M) - sum(a[i]);add(a[i], 1);}memset(tr, 0, sizeof tr);for (int i = n; i >= 1; i--) {times[i] += sum(a[i] - 1);add(a[i], 1);}long long res = 0;for (int i = 1; i <= n; i++) {res += (long long)(1 + times[i]) * times[i] / 2;	//注意根据题目条件，答案要求等差数列的和}cout << res;return 0;
}

这篇关于AcWing 1215. 小朋友排队 （树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---