Problem
给出两个长度均为 \(n\) 的数组 \(a\) 和 \(b\)，其中 \(a_i\) 中有一些位置是 。你需要将 \(a\) 中若干个 \(0\) 修改成其他的数，要求最终的数组 a 满足：
-
\(\{a_i\}\{b_i\}\) 中，所有数都是 \([0,x]\) 之间的整数;
-
所有正整数在 \(\{a_i\}\) 和 \(\{b_i\}\) 中的出现次数加起来不超过 \(1\);
在此基础上，设 \(p\) 为 “随机两个 \([1,n]\) 之间的整数 \(i, j\)” 后，“\(a_i > b_j\)” 这一事件发生的概率，要求选择一种修改 \(\{a_i\}\) 的方式，使得 \(\vert p - 0.5 \vert\) 最小。
要求返回使得 \(\vert p - 0.5 \vert\) 最小的 \(p\)。如果存在多个 \(p\)，输出较小的那个。
\(n \le 50, x \le 10^9\)
Input
第一行一个正整数 \(n\)，代表序列的长度。
第二行个整数，代表数组 \(a\)。
第三行个整数，代表数组 \(b\)。
第四行一个正整数，代表 \(x\)。
Output
输出仅一行，一个小数 \(p\)。
精度误差在 \(10^{-6}\) 以内。
Sample
Input 1
4
0 2 7 0
6 3 8 10
12
Output 1
0.4375
Solution
由于 \(a\) 中每一个元素会对 \(b\) 中元素进行比较，所以改变 \(b\) 中元素的顺序不影响答案。将 \(b\) 数组排序，这样可以快速地知道对于 \(a\) 中每一个非 \(0\) 元素，\(b\) 中有多少元素大于它。
同时，\(b\) 数组也将区间 \([0,x]\) 分成若干个连续的段，每段中的数对答案的贡献是相同的。此时原问题转化成了一个多重背包问题，每种物品有相应的贡献和数量，最终计算概率求出 \(p\) 值。
可以采用二进制优化，但我选择使用 \(bitset\) 来减小空间。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<iomanip>
using namespace std;
const int kmax = 55;
int n, k, a[kmax], b[kmax];
int w[kmax], c;
int res = -1e9;
bitset<kmax * kmax> f[kmax];
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
k += !a[i]; // 计算有多少个0
}
for(int i = 1; i <= n + 1; i++) {
cin >> b[i];
}
b[n + 1]++; // 右闭区间转开区间
sort(b + 1, b + n + 1); // 排序
for(int i = 1; i <= n; i++) {
w[i] = min(b[i + 1], b[n + 1]) - b[i] - 1; // 求区间
for(int j = 1; j <= n; j++) {
if(a[j] > b[i]) c++; // 计算原先有多少对
if(b[i] < a[j] && a[j] < b[i + 1]) w[i]--; // a中原先的数不能选
}
}
for(int i = 0; i <= k; i++) {
f[i][c] = 1; // 初始化
}
for(int i = 1; i <= n; i++) { // 多重背包
for(int j = 1; j <= w[i] && j <= k; j++) {
for(int l = k - 1; l >= 0; l--) {
f[l + 1] |= f[l] << i; // bitset 转移
}
}
}
for(int i = 0; i <= n * n; i++) {
if(!f[k][i]) continue; // 该状态无法实现
if(abs(n * n - 2 * res) <= abs(n * n - 2 * i)) continue; // 不够优
res = i;
}
cout << fixed << setprecision(9) << 1.0 * res / n / n << '\n';
return 0;
}