JZTXT

随机序列

发布时间 2023-07-13 20:27:45作者: ereoth

Problem

给出两个长度均为 \(n\) 的数组 \(a\) 和 \(b\)，其中 \(a_i\) 中有一些位置是 。你需要将 \(a\) 中若干个 \(0\) 修改成其他的数，要求最终的数组 a 满足：

  1. \(\{a_i\}\{b_i\}\) 中，所有数都是 \([0,x]\) 之间的整数;

  2. 所有正整数在 \(\{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];
    }
    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]--;
        }
    }
    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;
            }
        }
    }
    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;
}