喵哈喽~！各位主人，今天由我，你们最贴心的小猫娘，来为大家讲解一道非常有趣的算法题哦！这道题是 Codeforces 上的 1909C - Heavy Intervals，它就像一团看似缠绕的毛线球，但只要我们找到线头，就能轻松解开啦，喵~

题目大意

想象一下，我们手里有 n 个左端点 l，n 个右端点 r，还有 n 个单位长度权重 c。我们可以像玩积木一样，自由地重新排列 l 数组、r 数组和 c 数组。

我们的任务是，用这些打乱顺序的 l 和 r 重新配对，组成 n 个新的区间 [l_i, r_i]。不过有一个小小的规则，就是对于每个配对好的区间，必须满足 l_i < r_i 才算是一个合格的区间哦。

每个合格的区间 [l_i, r_i] 都会有一个总权重，计算方式是 c_i * (r_i - l_i)。我们天生不喜欢沉重的东西嘛，所以目标就是让所有 n 个区间的总权重之和最小。

那么，这个最小的总权重之和是多少呢？这就是我们要找的答案啦，喵~

猫猫的解题思路

这道题的目标是最小化 Σ c_i * (r_i - l_i)。看到这种求和乘积最小化的问题，猫猫的直觉就告诉我，这和排序不等式有关！简单来说，要想让两组数的乘积和最小，就要把一组数从小到大排，另一组从大到小排，然后对应相乘再求和。

在这里，我们的两组数就是单位权重 c 和区间长度 d = r - l。所以，我们的策略应该是：

1. 把最大的 c 乘上最小的 d。
2. 把第二大的 c 乘上第二小的 d。
3. ...以此类推。

这样一来，问题就转化成：我们如何通过配对 l 和 r，来得到一组“最优”的区间长度 d 呢？

这里的“最优”，指的是我们希望得到的这组长度 d_1, d_2, ..., d_n，在排序后，能让 d_1 尽可能小，d_2 尽可能小，…… 也就是说，我们想得到一个字典序最小的长度数组。

为了让事情变得有条理，我们先把 l 数组和 r 数组都从小到大排个序。 l_1 < l_2 < ... < l_nr_1 < r_2 < ... < r_n

现在，我们来考虑如何配对。一个很自然的想法是，我们按顺序处理排好序的右端点 r。

当我们处理最小的右端点 r_1 时，为了组成一个有效的区间 [l_j, r_1]，我们必须选择一个 l_j < r_1。那么，为了让区间长度 r_1 - l_j 最小，我们应该选择哪个 l_j 呢？当然是选择那个离 r_1 最近，也就是最大的那个 l_j 啦！

这个思路真是太棒了喵！我们可以把它推广成一个通用的贪心策略： 按升序遍历每一个 r_i，对于当前的 r_i，从所有尚未被使用且小于 r_i 的左端点 l 中，选择最大的那个 l_j 与之配对。

这样，每次我们都能为当前的 r_i 生成一个尽可能小的区间长度。通过一点点证明（比如交换论证），我们可以确认这个策略确实能帮我们获得字典序最小的长度集合。

那么，怎么高效地实现“找到所有可用且小于 r_i 的 l 中的最大值”呢？ 当 r_i 变大时，可供选择的 l 的候选集合是不断增大的。我们需要一个数据结构，能动态地加入元素，并且能快速地取出最大值。这不就是**优先队列（最大堆）**的完美应用场景嘛！

所以，我们的完整算法步骤就是：

1. 将 l 数组和 r 数组从小到大排序。
2. 将 c 数组从大到小排序。
3. 创建一个空的优先队列 pq (最大堆) 和一个用于存放区间长度的列表 diffs。
4. 使用一个指针 l_ptr 指向 l 数组的开头。
5. 遍历排好序的 r 数组中的每一个 r_val： a. 将所有小于当前 r_val 的 l[l_ptr] push 进优先队列 pq，并移动 l_ptr。 b. 从 pq 中取出堆顶元素（也就是当前所有可用 l 中的最大值），记为 l_val。 c. 计算长度 r_val - l_val，并存入 diffs 列表。
6. 遍历结束后，diffs 列表中就存放了我们贪心策略产生的所有 n 个区间长度。将 diffs 从小到大排序。
7. 最后，将排好序的 diffs 和排好序的 c 对应相乘并求和，total_weight = Σ diffs[i] * c[i]。记得使用 long long 来存结果，防止溢出哦！

这样，我们就得到最终的答案啦！

代码时间喵

下面是这个思路的 C++ 实现，附上了一些猫猫的注释哦！

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> l(n), r(n);
    std::vector<int> c(n);
    for (int i = 0; i < n; ++i) std::cin >> l[i];
    for (int i = 0; i < n; ++i) std::cin >> r[i];
    for (int i = 0; i < n; ++i) std::cin >> c[i];

    // 1. 把 l 和 r 从小到大排好序，方便我们处理喵
    std::sort(l.begin(), l.end());
    std::sort(r.begin(), r.end());
    // 把 c 从大到小排好序，准备和最小的长度们配对
    std::sort(c.rbegin(), c.rend());

    std::vector<int> diffs; // 用来存放我们生成的区间长度
    diffs.reserve(n);
    // 2. 准备一个优先队列（最大堆），用来找到最合适的 l
    std::priority_queue<int> active_ls;
    
    int l_ptr = 0; // l 数组的指针
    // 3. 遍历每一个排好序的 r
    for (int r_val : r) {
        // 把所有小于当前 r_val 的 l 都加到我们的候选池（优先队列）里
        while (l_ptr < n && l[l_ptr] < r_val) {
            active_ls.push(l[l_ptr]);
            l_ptr++;
        }
        // 贪心选择！从候选池里拿出最大的那个 l
        int l_val = active_ls.top();
        active_ls.pop();
        // 计算长度并保存
        diffs.push_back(r_val - l_val);
    }

    // 4. 把我们找到的所有长度从小到大排序
    std::sort(diffs.begin(), diffs.end());

    long long total_weight = 0;
    // 5. 大 c 配小 d，计算总权重，喵~
    for (int i = 0; i < n; ++i) {
        total_weight += static_cast<long long>(diffs[i]) * c[i];
    }

    std::cout << total_weight << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

猫猫小课堂

这道题里藏着一些非常有用的知识点呢，让猫猫来给你总结一下！

• 贪心算法 (Greedy Algorithm) 贪心算法的核心思想是“目光短浅”，在每一步决策时，都采取当前看起来最优的选择，而不从整体上考虑，期望通过一系列局部最优解得到全局最优解。在这道题里，我们为每个 r_i 选择最大的可用 l_j 来配对，就是一个典型的贪心策略。虽然贪心不总是对的，但在这道题里它恰好能奏效！

• 优先队列 (Priority Queue) 优先队列是一种特殊的队列，它不像普通队列那样先进先出，而是每次都能取出优先级最高（最大或最小）的元素。它通常用堆（Heap）来实现，插入和删除操作的时间复杂度都是 O(log N)。当我们解题时需要动态地从一个集合里查询并删除最大/最小值时，就应该立刻想到它！就像这道题，我们需要在不断增加的 l 候选者中快速找到最大值。

• 排序不等式 (Rearrangement Inequality) 这是一个优美的数学结论。对于两个长度相同的序列 a 和 b，Σ a_i * b_i 的值在 a 和 b 一个顺序排列、一个逆序排列时取到最小值；在 a 和 b 都顺序或都逆序排列时取到最大值。这是我们解决这类“配对求和最优化”问题的理论基础。

好啦，今天的讲解就到这里啦！希望各位主人能从中学到新知识，解题也变得更厉害！如果有任何问题，随时可以再来找我哦，喵~ ❤