题目分析
本题要求我们对n个小朋友按身高从低到高排序,并且每次只能交换相邻两个小朋友的顺序。
排序方法每次只能交换相邻两个小朋友的顺序,因此不难想到排序方法可能是冒泡排序。
冒泡排序也是每次只能交换相邻两个元素的位置。冒泡排序本质上是利用了“逆序对”的思想,
其通过每一次对相邻两个元素位置的交换,每一次最多只能减少一个逆序对的数量。
(注:必须是交换“相邻”两个元素的位置)
根据以上冒泡排序的大致思想可见,不论是经过什么样的排序方法,只要是这类通过交换
相邻元素顺序的方法,假设原数组有k个逆序对,那么至少要经过k次对相邻元素的交换,才能
使原数组按照从小到大(或从大到小)的顺序排列好。
那么冒泡排序是否为这类排序方法的最优解呢?
答案是肯定的,冒泡排序每次交换只会对相邻位置的逆序对进行元素的位置交换,即冒泡
排序的每一次对两相邻元素位置上的交换操作,都会减少一个逆序对,因此冒泡排序一定可以
在k次位置交换后让原数组排列好。
利用贪心的思想:我们分析得出对于原数组中的每一个元素,假设其前面有k1个数,后面
有k2个数可以与其组成逆序对。因此对于这个元素来说,最少需要交换 k1+k2次位置,那么冒
泡排序对每个元素是否都能做到最少交换次数呢?
答案是肯定的,假设每一个元素都能用最少的交换次数到达自己应该处于的位置,那么数
组中所有元素需要交换的次数之和就是2k,即为逆序对数量的2倍,利用冒泡排序可以达到。
所以这一题可以转换为求原数组中每一个元素可以组成的逆序对数量,如果大家做过算法
基础课中“逆序对数量”一题的话,不难想到该题可以使用“归并排序”去求解每一个元素的逆序
对数量。
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
LL num[N];
struct Query
{
int idx, h;
}q[N], tmp[N];
void merge_sort(Query q[], int l, int r)
{
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r)
{
if(q[i].h <= q[j].h)
{
//在区间[mid+1, r]中,[mid+1, j-1]内的元素都是小于i对应的元素的。
//即在之前的i,j指针的遍历中,j之前的元素都与i交换过。
num[q[i].idx] += j - (mid + 1);
tmp[k ++] = q[i ++];
}
else
{
//在区间[l, mid]中,[i, mid]内的元素都是大于j对应的元素的,即都可
//以与j对应的元素组成逆序对。
num[q[j].idx] += mid - i + 1;
tmp[k ++] = q[j ++];
}
}
while(i <= mid)
{
num[q[i].idx] += j - (mid + 1);
tmp[k ++] = q[i ++];
}
while(j <= r)
{
tmp[k ++] = q[j ++];
}
for(int i = l, j = 0; i <= r; i ++, j ++)
q[i] = tmp[j];
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
{
int height;
scanf("%d", &height);
q[i] = {i, height};
}
merge_sort(q, 0, n - 1);
LL ans = 0;
for(int i = 0; i < n; i ++)
{
//cout << q[i].h << " ";
//cout << num[i] << " ";
//cout << (1 + num[i]) * num[i] / 2 << " ";
ans += (1 + num[i]) * num[i] / 2;
}
cout << ans << endl;
return 0;
}