2025 ICPC Asia Manila Regional（2025 ICPC 亚洲 菲律宾 马尼拉）——D. Drinking Culture（把概率，转化为可行域面积占总面积的比重，这一点对两参数随意取的概率问题特别有用，三参数随意取的就是算体积占比？我猜）

题目大意

题目总结

Bob 有 $n$ 瓶酒精饮料，标号为 $1$ 到 $n$。已知第 $i$ 瓶饮料包含 $v_i$ 单位的液体体积，其中有 $a_i$ 单位是纯酒精（$0 \le a_i \le v_i$）。因此，第 $i$ 瓶饮料的酒精浓度为 $a_i / v_i$。每瓶饮料是完全均匀的，从中取出任意体积的液体，其酒精浓度均保持不变。

Bob 可以从这些瓶子中选择任意组合，并从每瓶中取出任意体积（不必须为整数）的液体进行混合。

现在提出一个挑战：
令 $V = \sum_{i=1}^n v_i$ 为所有瓶子中液体的总体积。
在 $[0, V]$ 区间内均匀随机生成一个实数 $s$（目标总体积）；
在 $[0, 1]$ 区间内均匀随机生成一个实数 $f$（目标酒精浓度）。

请计算：Bob 能够成功调配出总体积恰好为 $s$、且酒精浓度恰好为 $f$ 的饮品的概率是多少？（输出结果与标准答案的绝对或相对误差需不超过 $10^{-8}$）。

输入格式
第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$）。
第二行包含 $n$ 个整数，依次为 $v_1, v_2, \dots, v_n$（$1 \le v_i \le 10^9$）。
第三行包含 $n$ 个整数，依次为 $a_1, a_2, \dots, a_n$（$0 \le a_i \le v_i$）。

样例输入

3
350 750 330
140 131 16

样例输出

0.19356182654786474591

样例解释
在这个样例中，所有液体的总体积 $V = 350 + 750 + 330 = 1430$。

我们可以考虑两种具体的情况：
第一种情况：假设生成的 $s = 500$ 且 $f = \frac{3}{13}$。此时 Bob 是可以成功调配的。例如，他可以从第 $1$ 瓶中取出 $\frac{97750}{377}$ 单位的液体，从第 $3$ 瓶中取出 $\frac{90750}{377}$ 单位的液体。
调配出的总体积为 $\frac{97750}{377} + \frac{90750}{377} = \frac{188500}{377} = 500$。
调配出的酒精浓度为：

$$\frac{\frac{97750}{377} \times \frac{140}{350} + \frac{90750}{377} \times \frac{16}{330}}{500} = \frac{3}{13}$$

第二种情况：假设生成的 $s = 814$ 且 $f = 0.1234567$。此时 Bob 是无法完成调配的，因为利用他现有的饮料集合无法混合出该体积和浓度的饮品。

综合考虑所有可能在给定范围内均匀生成的 $s$ 和 $f$ 的数值对 $(s, f)$，Bob 能够成功调配的概率约为 $0.19356182654786474591$。

思路讲解

把概率，转化为可行域面积占总面积的比重，这一点对两参数随意取的概率问题特别有用。

具体而言，我们的这个分段函数应该长这样：

其不定积分是长这样的，带进去值，算一下定积分即可。

AC代码

AC
https://qoj.ac/submission/2106344
AC
https://codeforces.com/gym/106262/submission/365722146

源代码

/**
 * Problem: D. Drinking Culture
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/D
 * Created: 2026-03-07 17:50:25
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = long double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct V_A {
    ll v,a;
    // concentration
    DB c;
};
DB calVal(ll A,ll V,DB c,ll x) {
    if (x<=0) {
        return 0;
    }
    DB res=A*log(x)+c*x-c*V*log(x);
    return res;
}
void Solve() {
    ll N;
    cin >> N;
    // vector<ll> A(N+2),V(N+2);
    vector<V_A> wine_inc(N+2);
    ll sumv=0;
    for (int i=1;i<=N;++i) {
        cin>>wine_inc[i].v;
        sumv+=wine_inc[i].v;
    }
    for (int i=1;i<=N;++i) {
        cin>>wine_inc[i].a;
        wine_inc[i].c=DB(wine_inc[i].a)/wine_inc[i].v;
    }
    vector<V_A> wine_dec=wine_inc;
    sort(wine_inc.begin()+1,wine_inc.begin()+N+1,[](const V_A &a,const V_A &b) {
        return a.c<b.c;
    });
    sort(wine_dec.begin()+1,wine_dec.begin()+N+1,[](const V_A &a,const V_A &b) {
        return a.c>b.c;
    });
    DB mn_area=0;
    do {
        ll upA=0;
        ll upV=0;
        for (int i=1;i<=N;++i) {
            ll curV=upV+wine_inc[i].v;
            mn_area+=calVal(upA,upV,wine_inc[i].c,curV)-calVal(upA,upV,wine_inc[i].c,upV);
            upA=upA+wine_inc[i].a;
            upV=upV+wine_inc[i].v;
        }
    }while (false);
    DB mx_area=0;
    do {
        ll upA=0;
        ll upV=0;
        for (int i=1;i<=N;++i) {
            ll curV=upV+wine_dec[i].v;
            mx_area+=calVal(upA,upV,wine_dec[i].c,curV)-calVal(upA,upV,wine_dec[i].c,upV);
            upA=upA+wine_dec[i].a;
            upV=upV+wine_dec[i].v;
        }
    }while (false);
    DB area=mx_area-mn_area;
    DB ans=area/sumv;
    cout<<fsp(15)<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2106344
AC
https://codeforces.com/gym/106262/submission/365722146

*/

心路历程（WA，TLE，MLE……）

注意，分段函数不是线性的，而是一个分段反比例函数。

不要一会用 x，一会用 v，但是代表同一个意思。