BNDSOJ#1034 题解

题目链接

首先将 $a$ 数组和 $b$ 数组从小到大排序，显然顺序不影响答案。

设 $k_i$ 是满足 $b_{k_i}\leq a_i\leq b_{k_{i+1}}$的最小的数，那么题目要求的就是下面的这个式子：

$\begin{aligned} &\sum_{i = 1}^n \dfrac{\sum_{j = 1}^{k_i}(a_i-b_j)^2-\sum_{j = k_i + 1}^n{(a_i-b_j)}^2}{n}\\ =&\sum_{i=1}^n{\dfrac{a_i^2\times (2\times k_i-n)-2\times a_i\times \sum_{j=1}^{k_i}{b_j}+\sum_{j = 1}^{k_i}{b_j^2}+2\times a_i\times \sum_{j=k_i+1}^{n}{b_j}-\sum_{j = k_i+1}^{n}{b_j^2}}{n}} \end{aligned}$

稍微变形一下我们就可以发现这个式子只需要求某一段 $\sum{b_i}$ 和 $\sum{b_i^2}$ 就行了，其他的都可以 $O(1)$ 求出，就自然地想到前缀和。

前缀和预处理 $\sum{b_i}$ 和 $\sum{b_i^2}$ ，按上面的那个式子统计答案即可，复杂度 $O(n)$。

需要注意的是，预处理前缀和时需要先除一个 $n$，否则（大概）会越界，而且要开long double，否则会出一些奇怪的错误。

代码：

#include <bits/stdc++.h>
using namespace std;
long double read() {
    long double ret = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-') ? -f : f, ch = getchar();
    while (ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}
long double n, a[50005], b[50005], sum1[50005], sum2[50005], ans = 0, k[50005];

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n; ++i) b[i] = read();
    sort(a + 1, a + (int)n + 1);
    sort(b + 1, b + (int)n + 1);
    for (int i = 1; i <= n; ++i) {
        sum1[i] = sum1[i - 1] + b[i] / n; // 前缀和
        sum2[i] = sum2[i - 1] + b[i] * b[i] / n; // 前缀平方和
    }
    for (int i = 1, j = 1; i <= n; ++i) {
        while (a[i] > b[j] && j <= n) ++j;
        k[i] = j - 1;
    } // 预处理出ki
    for (int i = 1; i <= n; ++i) {
        ans += a[i] / n * (2 * k[i] - n) * a[i];
        ans += -2 * a[i] * sum1[(int)k[i]] + sum2[(int)k[i]];
        ans -= -2 * a[i] * (sum1[(int)n] - sum1[(int)k[i]]) + sum2[(int)n] - sum2[(int)k[i]];
    } // 根据上面的式子统计答案
    printf("%.1Lf", ans); // long double的输出是 %Lf
    return 0;
}

😏🤠🤠🤠