题解：P12297 [ICPC 2022/2023 WF] 三种骰子

· · 题解

骰子 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;
}