闲话
现在是8:00
我一个字没写
我就看我什么时候能写完这博客
现在是 8:40
我水完了
关于某个奇怪的题单
某个奇怪的人突然就给我了
说“我没写题解 你要继承我的遗志 把这里面的题都写了题解”
然后 ta 就 *** 了
然后我就开贺了
于是似乎最近不闲的闲话部分有话题了
希望能一天一道
“贺就完了”，某个奇怪的人说
図鑑に載ってた宇宙の話を
毎日読んでいた
最後のページに
世界の真理があると思っていた
でも時間が経って大きくなって
だんだん大人の匂いになって
そんなことは諦めた
杂题
你要抓神奇宝贝！现在一共有 \(n\) 只神奇宝贝。
你有 \(a\) 个『宝贝球』和 \(b\) 个『超级球』。
『宝贝球』抓到第 \(i\) 只神奇宝贝的概率是 \(p_i\)，『超级球』抓到的概率则是 \(u_i\)。
不能往同一只神奇宝贝上使用超过一个同种的『球』，但是可以往同一只上既使用『宝贝球』又使用『超级球』（都抓到算一个）。
请合理分配每个球抓谁，使得你抓到神奇宝贝的总个数期望最大，并输出这个值。\(n \leq 10^5\)。
solution1
考虑一个dp。平凡地，我们设 \(f[i][j][k]\) 表示抓了前 \(i\) 只神奇宝贝，用了 \(j\) 只普通球， \(k\) 只超级球。然后 \(O(n^3)\) 转移。
考虑一个优化。我们应该压掉一维，使得转移速度加快。这就让我们想到了什么？wqs二分。
经过打表 严密的证明和足够多的表 证明，这个dp在 \(k\) 维上是凸的。
证当然也可以证了：当 \(i,j\) 相同时，第一只超级球肯定抓期望最大的神奇宝贝，第二只抓次大……类推可证。
然后我们发现这个玩意在 \(j\) 维上也是凸的。
考虑wqs二分。我们首先让每个超级球有自己的花费，内层再让普通球有个自己的花费
然后wqs二分套wqs二分 写就完了
复杂度 \(O(n \log^2 n)\)
solution2
wqs二分
定义斜率k为使用超级球时多加的花费
然后二分斜率 每次扫一遍所有宝可梦，看如何选择
- 我都要！p + q - pq - k
- 只用干脆面 p
- 只用豆干 q - k
- 滚蛋！ 0
于是考虑每只宝可梦什么情况下是否选超级球
max(p + q - pq - k, p) - max(q - k, 0)
即为答案的变化量
内层sort一下选最优答案就行，复杂度 \(O(n \log^2 n)\)
题解说可以分讨避免内层排序
因此做到 \(O(n \log n)\)
code[solution2]
#include <bits/stdc++.h>
#define N 100005
#define rep(i,a,b) for ( register int (i) = (a); (i) <= (b); ++(i) )
#define pre(i,a,b) for ( register int (i) = (a); (i) >= (b); --(i) )
using namespace std;
double ans, p[N], q[N];
int n, a, b;
struct node {
int a0, a1;
// 用第一种/第二种粮与否
double x;
// 在此情况下当前wqs二分扰动后的可能性
bool operator < (const node & b) const {
return x > b.x;
}
} tmp[N];
bool check(double k) {
int c = 0; ans = 0;
rep(i,1,n) {
if (p[i] > p[i] + q[i] - p[i] * q[i] - k) tmp[i].a1 = 0, tmp[i].x = p[i];
else tmp[i].a1 = 1, tmp[i].x = p[i] + q[i] - p[i] * q[i] - k;
if (q[i] - k < 0) tmp[i].a0 = 0;
else tmp[i].a0 = 1, tmp[i].x -= q[i] - k, ans += q[i] - k;
} sort(tmp+1, tmp+1+n);
rep(i,1,a) c += tmp[i].a1, ans += tmp[i].x;
rep(i,a+1, n) c += tmp[i].a0;
return c < b;
}
signed main() {
cin >> n >> a >> b;
rep(i,1,n) cin >> p[i];
rep(i,1,n) cin >> q[i];
double l = 0, r = 1, mid = 0;
while (r - l >= 1e-11) {
mid = (l + r) / 2;
if (check(mid)) {
r = mid;
} else l = mid;
} printf("%.6lf", ans + b * mid);
return 0;
}