CF1165E
题意
给一个n,然后给出两个长度为n的数组a,b 我们定义$f(l,r)=\sum_{l<=i<=r}a_i*b_i$
你可以任意改变b数组的顺序,使得$\sum_{1<=l<=r<=n}f(l,r) $(以下称作②)最小,输出最小值mod 998244353
思路
很明显求贡献的题.
我们可以这样考虑,我们定义c_i=i*(n-i+1),表示在②中,ai*bi被计算的次数.然后②就变成了$\sum_{1<=i<=n}ciaibi$ ,由于a数组顺序固定,所以就可以定义d_i = a_i*c_i,然后式子就进一步化简为
$\sum_{1<=i<=n}di*bi$ 显然我们按照最小的bi匹配最大的di的原则,就可以得到最优的结果.
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
#define maxn (int)2e5 + 100
#define ll long long
#define fi first
#define se second
#define mod 998244353
pair<ll, int> d[maxn];
ll b[maxn], a[maxn];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
d[i].fi = (i)*1ll * (n - i + 1) * a[i];
d[i].se = i; // 此处是读错题所以多此一举了
}
sort(d + 1, d + 1 + n);
for (int i = 1; i <= n; ++i) {
cin >> b[i];
}
sort(b + 1, b + 1 + n, greater<ll>());
ll sum = 0ll;
for (int i = 1; i <= n; ++i) {
sum = (sum + d[i].fi % mod * b[i] % mod) % mod;
}
cout << sum << endl;
return 0;
}
