一、问题分析
这道题目要求我们计算将一个数组中的元素依次插入到一个初始为空的数组中时，所有插入操作的总代价。每次插入的代价定义为：
当前数组中严格小于插入元素的数目
当前数组中严格大于插入元素的数目
两者中的较小值
二、解题思路
我们可以使用树状数组(Fenwick Tree)来高效解决这个问题：
离散化处理所有可能的数值
使用树状数组维护当前数组中各数字的出现次数
对于每个插入元素，快速查询小于和大于它的元素数量
计算每次插入的代价并累加
class FenwickTree {
private:
vector<int> tree;
public:
FenwickTree(int size) : tree(size + 1) {}
void update(int index, int delta) {
while (index < tree.size()) {
tree[index] += delta;
index += index & -index;
}
}
int query(int index) {
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index & -index;
}
return sum;
}
};
class Solution {
public:
int createSortedArray(vector<int>& instructions) {
const int MOD = 1e9 + 7;
// 离散化处理
vector<int> sorted = instructions;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
FenwickTree ft(sorted.size());
int totalCost = 0;
for (int num : instructions) {
// 获取离散化后的索引
int rank = lower_bound(sorted.begin(), sorted.end(), num) - sorted.begin() + 1;
// 查询小于当前数的数量
int less = ft.query(rank - 1);
// 查询小于等于当前数的数量
int lessEqual = ft.query(rank);
// 当前数的出现次数
int same = lessEqual - less;
// 大于当前数的数量 = 总数 - 小于等于的数量
int greater = ft.query(sorted.size()) - lessEqual;
// 计算当前插入代价
int cost = min(less, greater);
totalCost = (totalCost + cost) % MOD;
// 更新树状数组
ft.update(rank, 1);
}
return totalCost;
}
};
