小朋友排队
归并排序 $O(nlogn)$
本质上还是个求逆序对的题,稍微复杂了一点而已。
逆序对的求法参见 逆序对的数量,可以用归并排序做。
由于小朋友的个数是 $10^5$,可以开个数组存小朋友被交换的次数。
在归并排序合并的时候,后面数组的第一个元素为当前最小值时,它被交换的次数就要加上它的逆序对的数量,也就是前面数组的当前元素数量:mid - i + 1
;
但同时,前面数组的元素也被经过了一次,所以交换次数要加1。为了避免循环,用cnt来存前面数组被经过的次数。当前面数组元素为当前最小值,要被取出时,交换次数加上cnt即可。
如果后面的数组先被取完,在复制前面数组的剩余元素时,也要依次加上cnt。
代码
// acwing 1215 小朋友排队
#include <iostream>
#include <cstdio>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n;
PII a[N], tmp[N]; // x存待排序的数,y存小朋友的编号
int h[N]; // 存每个小朋友的交换次数
void merge_sort(PII a[], int l, int r) {
if (l >= r) return ;
int mid = l + r >> 1;
merge_sort(a, l, mid), merge_sort(a, mid + 1, r);
int k = 0, i = l, j = mid + 1, cnt = 0; // cnt 存前数组被经过的次数
while (i <= mid && j <= r)
if (a[i].x <= a[j].x) {
h[a[i].y] += cnt; // 前数组元素被取出时,加上自己被经过的次数
tmp[k ++] = a[i ++];
} else {
h[a[j].y] += mid - i + 1; // 后数组元素被取出时,加上前数组的元素个数(比自己大还比自己靠前的数的个数)
cnt ++; // 前数组被经过的次数加1
tmp[k ++] = a[j ++];
}
while (i <= mid) {
h[a[i].y] += cnt; // 剩余元素也要加
tmp[k ++] = a[i ++];
}
while (j <= r) tmp[k ++] = a[j ++];
for (int i = l, j = 0; i <= r; i ++, j ++) a[i] = tmp[j];
}
int main() {
cin >> n;
for (int i = 1, x; i <= n; i ++ ) scanf("%d", &x), a[i] = {x, i};
merge_sort(a, 1, n);
long long res = 0; // 注意数据范围
for (int i = 1; i <= n; i ++) {
// cout << h[i] << endl;
res += (long long) h[i] * (h[i] + 1) >> 1;
}
cout << res << endl;
return 0;
}