P8613 [蓝桥杯 2014 省 B] 小朋友排队
题目描述
个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是 。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加 ，如果第二次要求他交换，则他的不高兴程度增加 （即不高兴程度为 ），依次类推。当要求某个小朋友第 次交换时，他的不高兴程度增加 。
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
输入格式
输入的第一行包含一个整数 ，表示小朋友的个数。
第二行包含 个整数 ，分别表示每个小朋友的身高。
输出格式
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
输入输出样例 #1
输入 #1
3
3 2 1
输出 #1
9
说明/提示
【样例说明】
首先交换身高为 和 的小朋友，再交换身高为 和 的小朋友，再交换身高为 和 的小朋友，每个小朋友的不高兴程度都是 ，总和为 。
【数据规模与约定】
对于 的数据，；
对于 的数据，；
对于 的数据，；
对于 的数据，，。
时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛
思路
这道题的常见解法就是正常的冒泡或者是选择，如果在一些题目数据卡的比较松的题还是蛮好过的，但是在这道题，很明显这样的解法是不可能的，那么我们就要找其他方法：每次计数的问题，我们可以通过去寻找数列的逆序数，那么在这道题中，我们可以通过两种解法：①树状数组，②归并排序
个人更推荐树状数组，处理方便，更加简洁，归并排序的逻辑可能稍微有点复杂
树状数组
//
// Created by 23264 on 2026/2/11.
//
#include<bits/stdc++.h>
using namespace std;
constexpr int MAX_HEIGHT = 1000005;
struct Child
{
int height;
long long swapNum;
long long unhappy;
};
int n;
vector<Child> child;
vector<int> tree;
int LowBit(int x)
{
return x & -x;
}
void Update(int x,int v)
{
for (int i = x;i < MAX_HEIGHT;i += LowBit(i))
{
tree[i] += v;
}
}
int Query(int x)
{
int res = 0;
for (int i = x;i > 0;i -= LowBit(i))
{
res += tree[i];
}
return res;
}
void solve()
{
for (int i = 0;i < n;i++)
{
int h = child[i].height + 1;
child[i].swapNum += (i - Query(h));
Update(h,1);
}
tree.assign(MAX_HEIGHT,0);
for (int i = n - 1;i >= 0;i--)
{
int h = child[i].height + 1;
child[i].swapNum += Query(h - 1);
Update(h,1);
}
for (int i = 0;i < n;i++)
{
child[i].unhappy = child[i].swapNum * (child[i].swapNum + 1) / 2;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
child.resize(n);
tree.resize(MAX_HEIGHT,0);
for (int i = 0;i < n;i++)
{
cin >> child[i].height;
child[i].unhappy = child[i].swapNum = 0;
}
solve();
long long sum = 0;
for (int i = 0;i < n;i++)
{
sum += child[i].unhappy;
}
cout << sum;
}归并排序
#include<bits/stdc++.h>
using namespace std;
struct Child {
int height;
int id; // 记录原始下标，以便把次数记在正确的人头上
};
int n;
vector<Child> temp; // 归并排序需要的临时数组
vector<Child> arr; // 存储小朋友
vector<long long> counter; // 记录每个人的交换次数 (使用 long long 防止溢出)
// 归并排序的核心：合并两个有序区间 [l, mid] 和 [mid+1, r]
void merge(int l,int mid,int r)
{
int i = l; // 左半边指针
int j = mid + 1; // 右半边指针
int k = l; // 临时数组指针
while (i <= mid && j <= r)
{
if (arr[i].height <= arr[j].height)
{
// 左边的数小（或相等），放入临时数组
// 此时，右半边已经有 (j - (mid + 1)) 个数被移走了
// 这些被移走的数都比 arr[i] 小，且原本在 arr[i] 后面
// 所以 arr[i] 的交换次数要加上这些数的数量
counter[arr[i].id] += (j - (mid + 1));
temp[k++] = arr[i++];
}
else
{
// 右边的数小，放入临时数组
// 此时，左半边剩下的 (mid - i + 1) 个数都比 arr[j] 大
// arr[j] 需要跨过这些数移到前面去
// 所以 arr[j] 的交换次数要加上左半边剩余的数量
counter[arr[j].id] += (mid - i + 1);
temp[k++] = arr[j++];
}
}
// 处理剩余的左半边
while (i <= mid)
{
// 同理，剩下的这些数，都要跨过右半边所有的数（即 r - mid 个）
// 也就是 j 此时已经跑到了 r+1，所以是 (j - (mid+1))
counter[arr[i].id] += (j - (mid + 1));
temp[k++] = arr[i++];
}
// 处理剩余的右半边
while (j <= r)
{
// 右边剩下的数不用统计逆序，因为左边都走完了，它们位置相对没变
temp[k++] = arr[j++];
}
// 将临时数组倒回原数组
for (int p = l;p <= r;p++)
{
arr[p] = temp[p];
}
}
// 递归分治
void mergeSort(int l,int r)
{
if (l >= r)
{
return;
}
int mid = (l + r) / 2;
mergeSort(l,mid);
mergeSort(mid + 1,r);
merge(l,mid,r);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
arr.resize(n);
temp.resize(n);
counter.resize(n,0);
for (int i = 0;i < n;i++)
{
cin >> arr[i].height;
arr[i].id = i; // 记住原始位置
}
// 开始归并排序
mergeSort(0,n - 1);
long long totalUnhappy = 0;
// 计算总不高兴程度
for (int i = 0;i < n;i++)
{
// 每个人总共交换了 counter[i] 次
// 利用公式 k*(k+1)/2 计算不高兴程度
long long k = counter[i];
totalUnhappy += k * (k + 1) / 2;
}
cout << totalUnhappy << endl;
}