蓝桥杯历届试题-小朋友排队

题目

题目链接

题解

树状数组求逆序对。

好早之前写过逆序对的三种求法 （看明白了树状数组求逆序对的方法后本题就很轻松了）

本题思路：

高矮不满足要求的相邻两个小朋友要互换位置，且二者的不高兴程度都是增加，所以对于某个小朋友而言，其左侧的高个会与其交换位置导致其不高兴程度增加，其右侧的矮个也会与其交换位置导致其不高兴程度增加。

这与逆序对的概念是不同的，逆序对可以理解为“某个数前面有多少比其大的数的个数”，但很显然，本题对于一个数而言，不仅要计算其前面比其大的还要计算后面比其小的。

我们会计算某个数前面比其大的数的个数，那只要再从后向前遍历数组，统计先插入的比当前数小的个数不就相当于计算某个数后面比其小的数的个数了嘛。

体现到代码上就是要正着遍历一遍再反着遍历一遍就可以求得每个小朋友交换的次数了，但是每个小朋友的交换次数并非该小朋友的不高兴程度。

小朋友不高兴程度为“从1一直加到该小朋友交换次数”，因为每次交换都会导致不高兴程度增加“该小朋友本轮交换的轮次”，所以不高兴程度为一个等差数列求和。

最后将每个小朋友的不高兴程度加起来就是答案。

本题主要考查两个点：

1. 树状数组计算逆序对。
2. 正向遍历 + 反向遍历。

代码 离散化代码

#include
using namespace std;
const int N = 1000010;
typedef long long ll;

int n;
ll ans;
ll c[N], nxd[N];

struct student {
	int idx;
	int idx_;
	int ht;
} stus[N];

bool byheight (student a, student b) {
	return a.ht  n;
	for (int i = 1;i > stus[i].ht, 
		stus[i].idx = i;
	
	sort (stus+1, stus+n+1, byheight);
	
	for (int i = 1, id = 0;i