题解：P8920 『MdOI R5』Variance

这是一道数学题。

首先，我们从方差的定义出发，方差的定义为了反映随机变量取值的离散程度的数值，方差越大，离散程度越大。又因为题目说了，保证 $a$ 数组的每一个对应数值小于等于 $b$ 数组的值，所以我们可以将函数划分为两个部分，前一部分全部选 $a$ 数组的值，后一部分全部选 $b$ 数组的值，这样保证了离散程度最大。然后枚举每一个分界值，找出最大的方差即为所求。

如果你的代码 $#5$ RE 了，注意 $n$ 是要设成 $int$ 的，如果 $WA$ 了的话就将 $n$ 前面加 $__int128$ 的。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, a[N], b[N];
__int128 maxn, a1[N], b1[N], af[N], bf[N];
inline void print(__int128 x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x < 10){
		putchar(x + 48);
		return ;
	}
	print(x / 10);
	putchar(x % 10 + 48);
}
inline __int128 fangcha(int id){
    __int128 abf = (af[id] + bf[id + 1]) * (__int128)n;
    __int128 ab = (a1[id] + b1[id + 1]) * (a1[id] + b1[id + 1]);
    return (abf - ab);
}
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];
        a1[i] += a1[i - 1] + (__int128)a[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> b[i];
    }
    for(int i = n; i >= 1; i--){
        b1[i] += b1[i + 1] + (__int128)b[i];
    }
    for(int i = 1; i <= n; i++){
        af[i] = (__int128)a[i];
        af[i] *= (__int128)a[i];
        af[i] += af[i - 1];
    }
    for(int i = n; i >= 1; i--){
        bf[i] = (__int128)b[i];
        bf[i] *= (__int128)b[i];
        bf[i] += bf[i + 1];
    }
    for(int i = 1; i <= n; i++){
        __int128 res = fangcha(i);
        maxn = max(maxn, res);
    }
    print(maxn);
    return 0;
}

管理大大求过！！！

支持壶关！！！