问题描述
有两个队伍 A 和 B, 每个队伍都有 n 个人. 这两支队伍之间进行 n 场 1 对 1 比赛, 每一场都是由 A 中的一个选手与 B 中的一个选手对抗. 同一个人不会参加多场比赛, 每个人的对手都是随机而等概率的. 例如 A 队有 A1 和 A2 两个人, B 队有 B1 和 B2 两个人, 那么 (A1 vs B1, A2 vs B2) 和 (A1 vs B2, A2 vs B1) 的概率都是均等的 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≤50. 对于 100% 的. 据, n≤50000; A [i], B [i] ≤50000.
Explanation
这道题乍看上去是一道 NP 复杂度的题 (不然为什么 30% 数据是 n=50 呢...... ) , 也就是\(O(n!)\). 但是 如果我们仔细分析一下, 就发现其实是一道多项式时间的题目. 固定任何一个位置来看, 某个人在这个位置比赛的概率一定是 \(\frac{1}{n}\). 进一步来讲, 也就是说, 我们可以将所有可能情况得到的分数 全除以一个 \((n-1)!\), 这样得到的就是两两选手之间分别比赛的得分, 而不是以任意序列排布得到 的分数 (可能不太好理解, 但是大概意思是这样的, 细节请读者自行脑补).
然后我们就得到一个 \(O(n^2)\) 的算法, 也就是把选手两两进行比较. 但是这中间有很多重复运算, 简单的用公式来解释一下就是:
\[\sum_{i}^{A} \sum_{j}^{B} ((A_i - B_j)^2\ if\ i \geq j\ else\ 0)\]
\[= \sum_{i}^{A} \sum_{j}^{B} (A_i ^ 2 - 2 A_i B_j + B_j ^ 2\ if\ i \geq j\ else\ 0)\]
\[= \sum_{i}^{A} (\sum_{j}^{B} (A_i ^ 2) - 2 A_i \sum_{j}^{B} B_j + \sum_{j}^{B} B_j^2)\]
然后就可以对b[] 的和与平方和进行维护. 这个操作可以用线段树和 Splay 树在\(O(logn)\) 时间内维护, 当然由于不修改, 也可以在\(O(1)\) 时间内进行查询.
如果略微用一下基数排序, 整个做法就被降到\(O(n)\) 以下. 但是这里毕竟用的是内置 sort 我懒得写 基数排序了对不对, 所以就是一个\(O(nlogn)\) 做法了~
Example Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long lli;
const int maxn = 50100;
const lli infinit = 0x007f7f7f7f7f7f7fll;
int n;
lli a[maxn], b[maxn];
lli a_sum[maxn], a_sqr_sum[maxn],
b_sum[maxn], b_sqr_sum[maxn]; // a_sum[i] = sum(a[1..i]), etc.
int main(int argc, char** argv)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%lld", &b[i]);
// Done inputting data, sorting
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n);
for (int i = 1; i <= n; i++) {
a_sum[i] = a_sum[i - 1] + a[i];
b_sum[i] = b_sum[i - 1] + b[i];
a_sqr_sum[i] = a_sqr_sum[i - 1] + a[i] * a[i];
b_sqr_sum[i] = b_sqr_sum[i - 1] + b[i] * b[i];
}
a[n + 1] = b[n + 1] = infinit;
// Sort complete, matching A in relative order
lli res_a = 0, res_b = 0;
int a_pos = 1, b_pos = 0;
for (; a_pos <= n; a_pos++) {
while (b[b_pos + 1] <= a[a_pos])
b_pos++;
res_a += b_pos * a[a_pos] * a[a_pos]
- 2 * a[a_pos] * b_sum[b_pos]
+ b_sqr_sum[b_pos];
}
// Matching B in relative order
a_pos = 0, b_pos = 1;
for (; b_pos <= n; b_pos++) {
while (a[a_pos + 1] <= b[b_pos])
a_pos++;
res_b += a_pos * b[b_pos] * b[b_pos]
- 2 * b[b_pos] * a_sum[a_pos]
+ a_sqr_sum[a_pos];
}
double res = (double)(res_a - res_b) / (double)n;
printf("%.1lf\n", res);
return 0;
}