自动搬运

查看原文

来自洛谷，原作者为

	ddxrS_loves_zxr 一个诗意的个性签名

搬运于2025-08-24 23:14:25，当前版本为作者最后更新于2025-06-16 15:42:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

骰子 $D_3$ 上每一面的取值只有 $O(n)$ 种。对于每种取值，我们可以算出如果它是朝上的一面与 $D_1$ 和 $D_2$ 的期望分数 $x_i,y_i$。

我们只说第一个问题，第二个问题是一样的。

现在的问题变成，给每一个 $i$ 分配一个非负整数系数 $c_i$，满足 $\frac{\sum c_ix_i}{\sum c_i}\ge 0.5$ 且 $\frac{\sum c_iy_i}{c_i}$ 最小。这个问题有两种解法。

第一，也是官方题解的做法。我们将一对数 $(x_i,y_i)$ 看成平面上的一个点，对所有的这些点求出一个下凸包，答案就是在凸包上与 $x=0.5$ 相交的 $y$ 最小的点。可以在 $O(n)$ 的复杂度内解决，总复杂度 $O(n\log n)$，瓶颈在离散化。

第二种，既然是求最小平均数，我们可以考虑二分答案。假设当前二分的平均数为 $mid$，那么就要求 $\sum c_i(x_i-0.5)\ge 0$ 且 $\sum c_i(y_i-mid)\le 0$。令 $p_i=x_i-0.5,q_i=y_i-mid$。

如果存在 $p_i\ge 0,q_i\le 0$ 肯定可行。否则让我们考虑 $p_i,q_i\le 0$ 和 $p_i,q_i\ge 0$ 的两类点。从两类点中分别选出一个，假设是 $j$ 和 $k$，如果存在 $\frac{p_j}{q_j}\le \frac{p_k}{q_k}$ 那么这两个点就能符合条件。于是找到最小的 $\frac{p_j}{q_j}$ 和最大的 $\frac{p_k}{q_k}$ 比较它们的大小即可。可以在 $O(n\log V)$ 的复杂度内解决，总复杂度 $O(n\log n+n\log V)$。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const double eps = 1e-10, inf = 1e16;
const int N = 6e5 + 5;
int n, m, lsh[N], cnt, suma[N], sumb[N];
double x[N], y[N];
struct node {
    double x, y;
} arr[N];
bool checkA(double mid) {
    double fl0 = inf, fl1 = 0;
    for (int i = 1; i <= cnt; i++) {
        arr[i].x = x[i] - 0.5, arr[i].y = y[i] - mid;
        if (arr[i].x >= 0 && arr[i].y <= 0)
            return true;
        else if (arr[i].x <= 0 && arr[i].y < 0)
            fl0 = min(fl0, arr[i].x / arr[i].y);
        else if (arr[i].x >= 0 && arr[i].y > 0)
            fl1 = max(fl1, arr[i].x / arr[i].y);
    }
    return fl0 < fl1;
}
bool checkB(double mid) {
    double fl0 = inf, fl1 = 0;
    for (int i = 1; i <= cnt; i++) {
        arr[i].x = x[i] - mid, arr[i].y = y[i] - 0.5;
        if (arr[i].x >= 0 && arr[i].y <= 0)
            return true;
        else if (arr[i].x <= 0 && arr[i].y < 0)
            fl0 = min(fl0, arr[i].x / arr[i].y);
        else if (arr[i].x >= 0 && arr[i].y > 0)
            fl1 = max(fl1, arr[i].x / arr[i].y);
    }
    return fl0 < fl1;
}
int main() {
#ifdef ddxrS
    freopen("sample.in", "r", stdin);
    freopen("sample.out", "w", stdout);
#else
    freopen("dice.in", "r", stdin);
    freopen("dice.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    vector<int> a(n);
    for (auto &p : a) {
        cin >> p;
        lsh[++cnt] = p, lsh[++cnt] = p + 1;
        if (p > 1)
            lsh[++cnt] = p - 1;
    }
    cin >> m;
    vector<int> b(m);
    for (auto &p : b) {
        cin >> p;
        lsh[++cnt] = p, lsh[++cnt] = p + 1;
        if (p > 1)
            lsh[++cnt] = p - 1;
    }
    sort(lsh + 1, lsh + cnt + 1);
    cnt = unique(lsh + 1, lsh + cnt + 1) - lsh - 1;
    for (auto &p : a) p = lower_bound(lsh + 1, lsh + cnt + 1, p) - lsh, suma[p]++;
    for (int i = 1; i <= cnt; i++) suma[i] += suma[i - 1];
    double sum = 0;
    for (auto &p : b) {
        p = lower_bound(lsh + 1, lsh + cnt + 1, p) - lsh, sumb[p]++;
        sum += suma[p - 1] + (suma[p] - suma[p - 1]) / 2.0;
    }
    for (int i = 1; i <= cnt; i++) sumb[i] += sumb[i - 1];
    sum = sum / m / n;//不要写成 sum /= n * m, n * m 爆 int 了。
    if (sum > 0.5) {
        swap(n, m), swap(a, b);
        for (int i = 1; i <= cnt; i++) swap(suma[i], sumb[i]);
    }
    for (int i = 1; i <= cnt; i++) {
        x[i] = (suma[i - 1] + (suma[i] - suma[i - 1]) / 2.0) / n;
        y[i] = (sumb[i - 1] + (sumb[i] - sumb[i - 1]) / 2.0) / m;
    }
    double l = 0, r = 1, mid, ansA = 0, ansB = 0;
    while (r - l > 1e-10) {
        mid = (l + r) / 2;
        if (checkA(mid))
            r = mid + eps, ansA = mid;
        else
            l = mid - eps;
    }
    l = 0, r = 1;
    while (l < r - eps) {
        mid = (l + r) / 2;
        if (checkB(mid))
            l = mid + eps, ansB = mid;
        else
            r = mid - eps;
    }
    cout << fixed << setprecision(12) << ansA << ' ' << ansB << '\n';
    return 0;
}