cf E. Two Arrays and Sum of Functions(贪心:排序不等式)

题意:给你两个数组a 和 b,然后定义了 f(l,r) = \sum_{l<=i<= r}^{`} ai *bi,最后让你求\sum_{1<=l<=r<=n}_{`}f(l,r)

思路:上式可化简为

最后可由排序不等式 对h 数组 和 B数组分别排个序,相乘取模即可。

AC Code:

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<cstdio>
#include<iomanip>
#include<sstream>
#include<algorithm>

using namespace std;
#define read(x) scanf("%d",&x)
#define readL(x) scanf("%lld",&x)
#define Read(x,y) scanf("%d%d",&x,&y)
#define sRead(x,y,z)  scanf("%d%d%d",&x,&y,&z)
#define FOR(x,y) for(int i = x;i <= y;++i)
#define gc(x)  scanf(" %c",&x);
#define mmt(x,y)  memset(x,y,sizeof x)
#define write(x) printf("%d\n",x)
#define FAST   ios::sync_with_stdio(false);cin.tie(0);
#define INF 0x3f3f3f3f
#define ll long long
const ll mod = 998244353;
#define pii pair<int,int>
#define pdd pair<double,double>
const int N = 1e6+5;
ll a[N];
ll b[N];
int main()
{
    FAST
    int n;
    cin>>n;
    for(int i = 1; i <= n;++i){
        cin>>a[i];
    }
    for(int i = 1;i <= n;++i){
        cin>>b[i];
    }
      for(int i = 1;i <= n;++i){
        a[i] = (ll)i*(n - i + 1)*a[i];//考虑贡献
    }
    sort(a + 1,a + n +1);
    sort(b + 1,b + n + 1,greater<ll>());
    ll ans = 0;
    for(int i = 1;i <= n;++i){
        ll tmp = (a[i] %mod* b[i]%mod)%mod;
        ans = (ans + tmp) % mod;
    }
    cout<<ans<<endl;

}

最后转载一位大佬的题解:

主要思路

 

原文链接:加载失败,请重新获取