CF1165E Two Arrays and Sum of Functions 题解

题目简述

已知两个长度均为 $n$ 的数组 $a$ 和 $b$。

给定一个函数：$f(l, r) = \sum \limits_{l \le i \le r} a_i \cdot b_i$。

你的任务是对数组 $b$ 中的元素以任意的顺序重新排序，使 $\sum \limits_{1 \le l \le r \le n} f(l, r)$ 的值最小。

题目分析

我们首先进行化简，发现题目中要求的实质上就是最小化 $\sum\limits_{l=1}^{n} \sum\limits_{r=l}^{n} \sum\limits_{i=l}^{r} a_i \times b_i$。接下来，我们考虑每一个 $a_i \times b_i$ 的贡献，由上述和式可知，$a_i \times b_i$ 出现的次数等于包含 $i$ 的区间的个数，设包含 $i$ 的区间为 $[l,r]$。显然 $1 \leq l \leq i$ 且 $i \leq r \leq n$。则 $l$ 共有 $i$ 个，$r$ 共有 $n-i+1$ 个，由乘法原理可得，包含 $i$ 的区间共有 $i \times (n-i+1)$ 个。即 $a_i \times b_i$ 共计算了 $i \times (n-i+1)$ 次。

有了上述的推导，题目要最小化的和式便可以化简成 $\sum\limits_{i=1}^{n} i \times (n-i+1) \times a_i \times b_i$，由题目可得 $i \times (n-i+1) \times a_i$ 是不变的，所以我们可以令 $c_i=i \times (n-i+1) \times a_i$，题目便被转化成最小化 $\sum\limits_{i=1}^{n} c_i \times b_i$。

此时，我们引入排序不等式，它的内容如下：

设有两个长度为 $n$ 的数列 $a$ 和 $b$，满足 $a$ 序列和 $b$ 序列单调不减，$c$ 序列是 $b$ 序列的乱序排列，则有：
$$\sum\limits_{i=1}^{n} a_i \times b_{n-i+1} \leq \sum\limits_{i=1}^{n} a_i \times c_i \leq \sum\limits_{i=1}^{n} a_i \times b_i$$

有了排序不等式，解法就呼之欲出了，我们倒序排列序列 $c$，再升序排列序列 $b$，最后求 $\sum\limits_{i=1}^{n} c_i \times b_i$ 即可，由排序不等式可证，此时的答案就是最小的了。

代码

#include<iostream>
#include<algorithm>
using namespace std;
#define int unsigned long long
const int N=2*1e5+10;
const long long mod=998244353;
int n,a[N],b[N],ans;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
	    if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
	    x=(x<<1)+(x<<3)+ch-48;
	    ch=getchar();
	}
	return x*f;
}
inline void write(int x)
{
    if(x<0)
	{
    	putchar('-');
		x=-x;
	}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
bool cmp(int x,int y)
{
	return x>y;
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
	}
	for(int i=1;i<=n;i++)
	{
		b[i]=read();
	}
	for(int i=1;i<=n;i++)
	{
		a[i]*=i*(n-i+1);
	}
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+n);
	for(int i=1;i<=n;i++)
	{
		a[i]%=mod;
		ans=(ans+a[i]*b[i])%mod;
		ans%=mod;
	}
	cout<<ans;
	return 0;
}