变形 - 2019.11.2 比赛

题面

【问题描述】

有两个队伍 A 和 B，每个队伍都有 n 个人。这两支队伍之间进行 n 场 1 对 1 比赛，每一场都是由 A 中的一个选手与 B 中的一个选手对抗。同一个人不会参加多场比赛，每个人的对手都是随机而等概率的。例如 A 队有 \(A_1\) 和 \(A_2\) 两个人，B 队有 \(B_1\) 和 \(B_2\) 两个人，那么 (\(A_1\) vs \(B_1\), \(A_2\) vs \(B_2\)) 和 (\(A_1\) vs \(B_2\), \(A_2\) vs \(B_1\)) 的概率都是均等的\(50\%\)。

每个选手都有一个非负的实力值。如果实力值为 \(X\) 和 \(Y\) 的选手对抗，那么实力值较强的选手所在的队伍将会获得 \((X-Y)^2\) 的得分。

求 \(A\) 的得分减 \(B\) 的得分的期望值。

【输入格式】

第一行一个数 \(n\) 表示两队的人数为 \(n\)。

第二行 \(n\) 个数，第 \(i\) 个数 \(A_i\) 表示队伍 A 的第 \(i\) 个人的实力值。

第三行 \(n\) 个数，第 \(i\) 个数 \(B_i\) 表示队伍 B 的第 \(i\) 个人的实力值。

【输出格式】

输出仅包含一个实数表示 A 期望赢 B 多少分。答案保留到小数点后一位（注意精度）。

【样例输入】

2
3 7
1 5

【样例输出】

20.0

【数据规模】

对于 \(30\%\) 的数据，\(n\le 50\)。

对于 \(100\%\) 的数据, \(n\le 50000\), \(A_i, B_i\le 50000\)。

解

期望计算不难。即为
\[\frac{1}{n}\sum_{1\le i,j\le n}\text{sgn}(A_i-B_j)(A_i-B_j)^2\].

按原样计算仅能得 30 分，需要变形。不难得到对于每个 \(j\in[1,n]\cap\mathbb{Z}\), 计算 \(\sum_{i=1}^{n}\text{sgn}(A_i-B_j)(A_i-B_j)^2\).
又因为 \(\text{sgn}(A_i-B_j)\) 的存在使得前缀和不能使用，不难想到二分来计算 \(\text{sgn}(A_i-B_j)=1\) 或 \(\text{sgn}(A_i-B_j)=-1\) 的区间。
有少数特殊情况，lower_bound()给出的下界不能直接用于运算，需要调整。

计算得这个界 \(s\) 后，有
\[-\sum_{i=1}^s(A_i-B_j)^2=-\sum_{i=1}^sa_i^2+2B_j\sum_{i=1}^sA_i-sB_j^2\\sum_{i=s+1}^n(A_i-B_j)^2=\sum_{i=s+1}^nA_i^2-2B_j\sum_{i=s+1}^nA_i+(n-s)B_j^2\]
计算前缀和 \(\text{apre}=(\sum_{j=1}^iA_j)_{i=1}^n\) 与平方前缀和 \(\text{apsq}=(\sum_{j=1}^iA_j^2)_{i=1}^n\) 后计算每个项都是 \(O(1)\) 的，总时间复杂度为 \(O(n\log{n})\).

程序

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
 
#define MAXN 50050
ll a[MAXN], b[MAXN], apre[MAXN], apsq[MAXN];
int n;
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    apre[0] = apsq[0] = 0;
    for (int i = 1; i <= n; i++) {apre[i] = apre[i - 1] + a[i]; apsq[i] = apsq[i - 1] + a[i] * a[i];}
//  apre[n + 1] = apre[n]; apsq[n + 1] = apsq[n];
     
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int s = lower_bound(a + 1, a + n + 1, b[i]) - a;
        if (a[s] > b[i]) s--;
        if (s == n + 1) s--;
//      cout << b[i] << ": " << s << endl;
        ans += (apsq[n] - 2 * apsq[s]) + 2 * b[i] * (2 * apre[s] - apre[n]) + (n - 2 * s) * b[i] * b[i];
    }
    printf("%.1Lf\n", (long double) ans / n);
    return 0;
}

变形 - 2019.11.2 比赛

原文：https://www.cnblogs.com/lrw04/p/11815816.html