2025 ICPC Asia Manila Regional（2025 ICPC 亚洲 菲律宾 马尼拉）——D. Drinking Culture（把概率，转化为可行域面积占总面积的比重，这一点对两参数随意取的概率问题特别有用，三参数随意取的就是算体积占比？我猜） · znzryb
## 题目大意
**题目总结**
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](https://qoj.ac/submission/2106344)
AC
[https://codeforces.com/gym/106262/submission/365722146](https://codeforces.com/gym/106262/submission/365722146)
::: 源代码
```cpp
/**
* 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，但是代表同一个意思。
