E. Two Arrays and Sum of Functions - 题解

比赛与标签

比赛: Codeforces Round 560 (Div. 3) 标签: greedy, math, sortings 难度: *1600

喵喵，题目说什么呀？

哈喽，各位算法大师们，喵~ 今天我们来解决一个看起来有点吓人，但其实非常有趣的题目哦！

题目给了我们两个长度都是 n 的数组 a 和 b。然后定义了一个函数 f(l, r)，它等于从 l 到 r 这个区间里所有 a[i] * b[i] 的和。

我们的任务是，可以任意地重新排列数组 b 里的元素，目标是让所有可能的 f(l, r) 的总和 Σ f(l, r) 变得最小最小。最后把这个最小的总和对 998244353 取模输出就好啦，喵~

简单来说就是：

输入: 整数 n，数组 a 和数组 b。
操作: 重新排列 b 数组。
目标: 最小化 Σ (a[i] * b[i] 对所有子数组求和) 的总和。
输出: 最小总和 % 998244353。

来和喵娘一起分析吧！

这个求和公式 Σ f(l, r) 里面套着另一个求和，看起来就像一个俄罗斯套娃，让人头晕眼花，的说。但是不要怕！让本喵娘带你一步步拆解它！

第一步：化繁为简，喵~

直接去想怎么排列 b 来让这个复杂的总和最小，肯定会把脑子绕成一团毛线球的！所以，我们换个思路。与其关注每个子区间的和，不如我们看看每个 a[i] * b[i] 这个“积项”到底被加了多少次呢？这就是所谓的贡献法思想，喵~

一个积项 a[i] * b[i] 会被包含在 f(l, r) 中，当且仅当这个区间 [l, r] 包含了下标 i，也就是 l <= i <= r。

我们来数一数，对于一个固定的下标 i (我们按0-based算，即 0 <= i < n)，有多少个区间 [l, r] 满足 0 <= l <= i <= r < n 呢？

l 的选择范围是 0, 1, ..., i，总共有 i + 1 种选择。
r 的选择范围是 i, i+1, ..., n-1，总共有 (n-1) - i + 1 = n - i 种选择。

所以，a[i] * b[i] 这个项在最终的总和里，总共被加了 (i + 1) * (n - i) 次！

这样一来，我们要求的那个超级复杂的总和 S，就可以被漂亮地简化成： S = Σ (a[i] * b[i] * (i + 1) * (n - i)) (对所有 i 从 0 到 n-1 求和)

第二步：贪心大法好，喵！

现在问题就清晰多啦！我们要重新排列 b 数组，来最小化 S。我们可以把 a[i] * (i + 1) * (n - i) 看作一个新的数值，我们叫它 A[i] 吧。那么我们的目标就是：最小化 S = Σ A[i] * b_{p(i)}，其中 p(i) 是 b 数组的一个排列。

这是一个经典的排序问题！想象一下，你有两堆数字，要把它们配对相乘再求和。要想让总和最小，你应该怎么做呢？

答案是：把一堆里最大的和另一堆里最小的配对，次大的和次小的配对，以此类推。这就是排序不等式 (Rearrangement Inequality) 的直观体现。

所以，我们的贪心策略就出来啦：

计算出新的系数数组 A，其中 A[i] = a[i] * (i + 1) * (n - i)。
将数组 A 升序排序（从小到大）。
将数组 b 降序排序（从大到小）。
将排序后的两个数组对应位置的元素相乘再求和，得到的就是最小的总和啦！

S_min = Σ A_{sorted}[i] * b_{sorted_desc}[i]

这样，我们就把一个复杂的问题转化成两次排序和一个简单的求和了，是不是很神奇呢？喵~

看喵娘的代码魔法！

下面就是把我们的思路变成代码实现啦，本喵娘加了详细的注释，方便你理解每一行都在做什么哦！

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 const long long mod = 998244353;
 int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
     int n;
    cin >> n;
    
    // 喵~ 首先读入n和两个数组a, b
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    // 核心步骤！我们不直接用a，而是计算每个a[i]的贡献系数
    // a[i]会被计算 (i+1)*(n-i) 次，所以我们直接把这个系数乘进去
    // 注意这里要用 1LL 来保证乘法是以 long long 类型进行的，防止溢出！
     for (int i = 0; i < n; i++) {
        long long c_i = (i + 1LL) * (n - i);
        a[i] = a[i] * c_i;
    }
    
    // 贪心策略的核心：把新的a数组升序排序
     sort(a.begin(), a.end());
    // 把b数组降序排序
    sort(b.begin(), b.end(), greater<long long>());
    
    // 这样就能让大的贡献系数乘上小的b[i]，小的贡献系数乘上大的b[i]，总和就最小啦~
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        // 计算每一对的乘积，并加到总和里
        // 记得每一步都要取模哦！先对因子取模再相乘，防止中间结果溢出
        long long term = (a[i] % mod) * (b[i] % mod);
        term %= mod;
        ans = (ans + term) % mod;
    }
    
    // C++的取模运算对负数结果不友好，虽然这里不会出现负数，
    // 但加上mod再取模是一个保险的好习惯喵
    ans %= mod;
    if (ans < 0) {
        ans += mod;
    }
    
    cout << ans << endl;
    
     return 0;
}

跑得快不快呀？

时间复杂度: O(N log N) 的说。整个算法最耗时的部分就是两个排序操作 sort(a.begin(), a.end()) 和 sort(b.begin(), b.end())，它们的时间复杂度都是 O(N log N)。其他部分，比如读入、计算贡献系数和最终求和，都只是 O(N) 的线性扫描。所以总的时间复杂度由排序决定，就是 O(N log N) 啦！
空间复杂度: O(N) 的说。我们主要使用了两个 vector 来存储数组 a 和 b，它们都需要 O(N) 的空间。所以空间复杂度就是 O(N) 呢。

喵喵小课堂

通过这道题，我们又学到了一些超有用的技巧，快拿小本本记下来！

贡献法思想: 这是解决复杂求和问题的利器！当遇到多重循环或者对所有子结构求和时，不妨换个角度，思考每个基本元素对最终答案的贡献是多少。这能大大简化问题，喵！
贪心与排序 (排序不等式): “最大配最小，总和才最小”这个贪心直觉在很多问题中都适用。当你要最小化/最大化配对乘积之和时，一定要先想到排序！
注意数据范围: a[i]、b[i] 和 n 的范围都挺大的，a[i] * (i+1) * (n-i) 很容易就会超出 32 位整数的范围。在编程时，要时刻对数据范围保持警惕，及时使用 long long 防止溢出，这是一个专业ACMer的好习惯哦！

希望这篇题解能帮到你！继续加油，你一定能成为更厉害的算法大师的，喵~！

E. Two Arrays and Sum of Functions - 题解 ​

比赛与标签 ​

喵喵，题目说什么呀？ ​

来和喵娘一起分析吧！ ​

第一步：化繁为简，喵~ ​

第二步：贪心大法好，喵！ ​

看喵娘的代码魔法！ ​

跑得快不快呀？ ​

喵喵小课堂 ​