题解：CF1165E Two Arrays and Sum of Functions

Rex01

2025-01-13 11:21:54

题解

CF1165E 题目传送门

题目大意

给定两个长度均为 n 的数组 a 和数组 b，定义函数 f(l, r) = \sum\limits_{i = l} ^ {r} (a_i \cdot b_i)。你的任务是重新排列数组 b 的元素，使 f(l,r) 的值最小。更具体的解释：就是要求对于区间 [1,n] 上所有子区间 [l,r] (1 \leq l \leq r \leq n)，函数 f(l,r) 的总和的最小值。

解决思路

有题目中的公式可以推断出

\begin{aligned} f(l, r) &= \sum\limits_{i = l} ^ {r} (a_i \cdot b_i)\\ &= (a_l \cdot b_l) + (a_{l + 1} \cdot b_{l + 1}) + (a_{l + 2} \cdot b_{l + 2}) + \cdots + (a_r \cdot b_r)\\ &\because l=C_{i}^{1}, r=C_{n-i+1}^{1}\\ &\therefore C_{i}^{1} \cdot C_{n-i+1}^{1} = i \cdot (n - i + 1)\\ &\therefore \sum\limits_{i = l} ^ {n} [a_i \cdot b_i \cdot (n - i + 1) \cdot i] \end{aligned}

随后再把推导出的公式融入进代码即可。

代码展示

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

const int N = 2e5 + 10;
const int mod = 998244353;
ll n, a[N], b[N], sum;

bool cmp(int a, int b)
{//从大到小排序函数
    return a > b; 
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i], a[i] *= (n - i + 1) * i;
    for(int i = 1; i <= n; i++)
        cin >> b[i];
    sort(a + 1, a + n + 1);//从小到大
    sort(b + 1, b + n + 1, cmp);//从大到小
    for(int i = 1;i <= n; i++)
    {
        sum %= mod;
        sum += a[i] % mod * b[i] % mod;
        sum %= mod;
    }
    cout << sum << endl;
    return 0;
}