durianp的blog
[蓝桥杯 2014 省 B] 小朋友排队
1. 题目详情
题目描述
$n$ 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是 $0$。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加 $1$，如果第二次要求他交换，则他的不高兴程度增加 $2$（即不高兴程度为 $3$），依次类推。当要求某个小朋友第 $k$ 次交换时，他的不高兴程度增加 $k$。
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
输入格式
输入的第一行包含一个整数 $n$，表示小朋友的个数。
第二行包含 $n$ 个整数 $H_1,H_2 \cdots H_n$，分别表示每个小朋友的身高。
输出格式
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
样例 #1
样例输入 #1
3
3 2 1样例输出 #1
9提示
【样例说明】
首先交换身高为 $3$ 和 $2$ 的小朋友，再交换身高为 $3$ 和 $1$ 的小朋友，再交换身高为 $2$ 和 $1$ 的小朋友，每个小朋友的不高兴程度都是 $3$，总和为 $9$。
【数据规模与约定】
对于 $10\%$ 的数据，$1 \le n \le 10$；
对于 $30\%$ 的数据，$1 \le n \le 1000$；
对于 $50\%$ 的数据，$1 \le n \le 10000$；
对于 $100\%$ 的数据，$1 \le n \le 100000$，$0 \le H_i \le 1000000$。
时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛
2. 解题思路
这个题目与之前做过的题目火柴排队很容易产生联想，因为同样一次只能交换相邻元素，同时也寻找步数最少的最优解。但火柴排队问题需要求得最少步数，而这个问题需要求得最少步数时每个元素的移动次数，如果硬套用火柴排队中的逆序对来做的话实现起来很麻烦。具体思路为，每个小朋友移动的次数 $t$，等于排在这个小朋友前面但是比这个小朋友高的小朋友总数 $h$ ，与排在这个小朋友后比这个小朋友矮的小朋友数s的和，$t=h+s$ ，也就是以该元素组成的所有逆序对数量。再根据每个 $t$ 求解不开心程度并求和即可。在我看到的题解中，这个思路基本上都使用了高级数据结构线段树，在我尝试使用归并排序实现这个思路时，发现难度很大，各种情况讨论比较复杂，一直没有写出正解，于是提出了一种更易于理解的思路。
归并排序的过程本质就是一个步数最少排序过程，它的每一步都是全局最优的。那么在归并排序的过程中，将排序的每一步都记录下来，就可以获得每个元素的 $t$ ——交换次数了。那么应该在什么地方进行记录呢？在解决每个归并排序的子问题时，元素可能会产生位置变化，而位置变化所需要的交换，在全局来说都是必要且最优的。而元素位置的变化量，就是解决这个子问题时，这个元素产生的必要交换的次数。那么在每个子问题解决完后，记录每个元素的位置改变量并逐子问题累加在一起，即可求得该元素的总交换数。
这个思路过程本质上是进行一次归并排序，时间复杂度为 $O(n\log_n)$ ，计算每个小朋友的不高兴程度用等差数列求和时间复杂度为 $O(n)$ ，因此该算法时间复杂度为 $O(n\log_n)$。
3. 实现代码
// https://www.luogu.com.cn/problem/P8613
// https://www.acwing.com/problem/content/description/1217/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
struct Child
{
int height;
LL unhappiness;
int originalIndex;
};
int n;
vector<Child> children;
void merge(int left, int mid, int right)
{
int i = left, j = mid + 1;
vector<Child> temp;
while (i <= mid && j <= right)
{
if (children[i].height <= children[j].height)
temp.push_back(children[i++]);
else
temp.push_back(children[j++]);
}
while (i <= mid) temp.push_back(children[i++]);
while (j <= right) temp.push_back(children[j++]);
for (int k = left; k <= right; k++) children[k] = temp[k - left];
}
void mergeSort(int left, int right)
{
if (left == right) return;
int mid = (left + right) >> 1;
mergeSort(left, mid);
mergeSort(mid + 1, right);
merge(left, mid, right);
for (int i = left; i <= right; i++)
{
// 累加位置变化量
children[i].unhappiness += abs(i - children[i].originalIndex);
// 重置初始位置
children[i].originalIndex = i;
}
}
int main() {
cin >> n;
children.resize (n);
for (int i = 0; i < n; i++)
{
cin >> children[i].height;
children[i].unhappiness = 0;
children[i].originalIndex = i;
}
mergeSort(0, n - 1);
LL totalUnhappiness = 0;
for (int i = 0; i < n; i++)
{
totalUnhappiness += ((1LL + children[i].unhappiness) * children[i].unhappiness) / 2LL;
}
cout << totalUnhappiness << endl;
return 0;
}
4. 相关链接
- 原题链接：[P8613 [蓝桥杯 2014 省 B] 小朋友排队 - 洛谷](https://www.luogu.com.cn/problem/P8613) 1215. 小朋友排队 - AcWing题库
- 相似题目题解：[[NOIP2013 提高组] 火柴排队 - 题解 - durianp - dup.asia](https://www.dup.asia/technique/noip2013-match/)
- 逆序对思路使用线段树和树状数组的做法：小朋友排队 - onlyblues - 博客园 (cnblogs.com)
评论(0)