B4466 [海淀区入门组 2025] 函数的和

Nostopathy · 2026-01-22 20:53:27 · 题解

考虑一个位置 i 的贡献被计算的次数，为区间左端点选在 [1,i] 的数量乘以右端点选在 [i,n] 的数量，即 i \times (n - i + 1)。

定义 w_i = i \times (n - i + 1) \times a_i。根据排序不等式，尽量选择更小的 w_i 乘更大的 b_i，可得到最小答案。

::::warning[注意]{open} 当心随处存在的越界问题，请随处取模，并转换类型为 long long。 ::::

::::success[AC 代码]

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int mod = 998244353;

int n, s, a[200005], b[200005];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] *= 1LL * i * (n - i + 1);
    }

    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
    }

    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1, greater<int>());

    for (int i = 1; i <= n; ++i) {
        s = (s + (a[i] % mod) * (b[i] % mod)) % mod;
    }

    cout << s;

    return 0;
}

::::