A21370. 函数的和（sum.cpp）
填空题
中等
知识点
题目描述
函数的和（sum.cpp）
题目描述
圣诞节联欢活动有一道数学思维题。给定两个长度为 n 的数组 a 和 b，定义函数 f (L, r) = Σ（aᵢ×bᵢ）（i 从 L 到 r）。重新排列数组 b 的元素，使得 Σf (L, r)（1≤L≤r≤n）的值尽可能小，答案对 998244353 取模后输出。
输入描述
第一行包含整数 n（1≤n≤2e5）；
第二行包含 n 个整数 a₁、a₂、…、aₙ（1≤aᵢ≤1e5）；
第三行包含 n 个整数 b₁、b₂、…、bₙ（1≤bᵢ≤1e5）。
输出描述
输出最小的 Σf (L, r) 值（对 998244353 取模）。
样例输入1
5
1 8 7 2 4
9 7 2 9 3样例输出1
646样例输入2
1
1000000
1000000样例输出2
757402647样例输入3
2
1 3
4 2样例输出3
20参考答案
#include<bits/stdc++.h>
#define ll long long
usingnamespacestd;
constint maxn = 2e5 + 10;
constint MOD = 998244353;
ll a[maxn], b[maxn];
ll weight[maxn]; // 存储每个位置的权重
int n;
int main()
{
cin >> n;
// 读取数组 a
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
// 读取数组 b
for(int i = 1; i <= n; i++)
{
cin >> b[i];
}
// 计算每个位置的权重 = a[i] * i * (n-i+1)
// 注意：这里先计算权重，不要取模
for(int i = 1; i <= n; i++)
{
weight[i] = a[i] * 1LL * i * (n - i + 1);
}
// 对权重升序排序（与 b 的降序匹配）
sort(weight + 1, weight + n + 1);
// 对 b 降序排序
sort(b + 1, b + n + 1, greater<ll>());
ll ans = 0;
// 根据排序不等式：权重小的乘以 b 大的，权重大的乘以 b 小的
for(int i = 1; i <= n; i++)
{
// 这里需要对 weight[i] 取模后再计算
ans = (ans + (weight[i] % MOD) * (b[i] % MOD)) % MOD;
}
cout << ans << endl;
return0;
}
上一题
下一题