1 条题解

  • 1
    @ 2024-1-24 16:00:41

    根据排序不等式,对于每个 aia_i,应该配对一个对应的 bjb_j,使得 aia_iaa 从大到小排序后的位置和 bjb_j 从小到大排序后的位置相同。

    另外还要考虑每个 aia_i 累加的数量。在这个序列中,包含 aia_i 的区间有 i×(ni+1)i \times(n-i+1) 个,所以只要在 aia_i 读入时,乘上个 i×(ni+1)i \times(n-i+1)

    核心代码
    
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e6 + 10;
    unsigned long long n, a[N], b[N], ans;
    int main()
    {
        cin >> n;
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
            a[i] *= i * (n - i + 1);
        }
        for(int i = 1; i <= n; i++)
            cin >> b[i];
        sort(a + 1, a + n + 1, greater<unsigned long long>());//greater可以用来从大到小排序
        sort(b + 1, b + n + 1);
        for(int i = 1; i <= n; i++)
            ans = (ans + a[i] % 998244353 * b[i] % 998244353) % 998244353;
        cout << ans << endl;
        return 0;
    }
    
    • 1

    【挑战题】两个数组和函数的和

    信息

    ID
    662
    时间
    2000ms
    内存
    256MiB
    难度
    2
    标签
    (无)
    递交数
    86
    已通过
    51
    上传者