CF739E Gosha is hunting 题解

题意：

你要抓神奇宝贝！现在一共有 $n$ 只神奇宝贝，而你有 $a$ 个『宝贝球』和 $b$ 个『超级球』。

『宝贝球』抓到第 $i$ 只神奇宝贝的概率是 $p_i$，『超级球』抓到的概率则是 $u_i$ 。

不能往同一只神奇宝贝上使用超过一个同种的『球』，但是可以往同一只上既使用『宝贝球』又使用『超级球』（都抓到算一个）。

请合理分配每个球抓谁，使得你抓到神奇宝贝的总个数期望最大，并输出这个值。

$2\le n \le 2000,~0 \le a,b \le n,~0 \le p_i,u_i \le 1$。

一道 wqs二分的好题呀

设 $f_{i,j,k}$ 表示前 $i$ 只神奇宝贝，用了 $j$ 个宝贝球和 $k$ 个超级球的最大期望，则

$f_{i,j,k} =\max\left\{ f_{i-1,j-1,k} +p_i,\,f_{i-1,j,k-1} + u_i,\,f_{i-1,j-1,k-1} + p_i +u_i - p_iu_i \right\}$

可以发现，当 $i,j$ 固定时，关于 $k$ 的函数 $f_{i,j,k}$ 是一个上凸壳。

这一点可能不太显然，参考 wqs二分的模型，我们会优先用收益大的超级球，则

$g(k) - g(k-1) \ge g(k + 1)-g(k)$

这意味着，随着 $k$ 的增大，$g(k)$ 关于点 $(k,g(k))$ 的切线斜率是单调递减的，即 $g(k)$ 为上凸函数

注意到这个单调递减了吗，我们可以去二分一条切线的斜率 $c$ 。

当 $c$ 固定时，我们考察这条切线过 $g(k)$ 上每个点时截距的最大值，这个截距显然是 $f(k)=g(k)-ck$

此时的 $f(k)$ 相当于每个物品的价值减少了 $c$ 时、不限制选的物品个数选出的最优方案。

当然我们不需要这个最优方案的价值，我们需要知道这个最优方案用了多少个物品。

例如，如果最优方案用了 $x < k$ 个物品，那说明我们需要小一些的 $c$ 。

最终当 $x=k$ 时，我们只需要把 $f(k)$ 加上 $ck$ 就是我们一开始需要的 $g(k)$ 了，即 $f_{i,j,k}$ 。

这么做的话时间复杂度是 $\mathcal{O}(n^2 \log n)$ 的，因为 $k$ 这一维可以贪心。

我们考察一个位置从不用超级球到用超级球，答案的增加量为

$\Delta_i = \max(p_i + u_i - p_iu_i - c, p_i) - \max(u - k_i, 0)$

实际上我们不用 dp $j$ 这一维，只需要按 $\Delta_i$ 排序即可（甚至可以分四种情况归并以省掉排序，这样少一个 log）

时间复杂度 $\mathcal{O}(n \log^2 n)$

代码：

// 2022-06-19 11:55:23
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
const double eps=1e-13;
int n,a,b;
double sum,p[N],q[N];
int dcmp(int x){if(fabs(x)<=eps)return 0;return x>eps?1:-1;}
bool ld(double a,double b){return b-a>eps;}
struct node
{
    double x; int a0,a1;
}t[N];
bool ck(double k)
{
    int i,c=0;sum=0;
    for(i=1; i<=n; i++)
    {
        if(ld(p[i]+q[i]-p[i]*q[i]-k,p[i]))
            t[i].a1=0,t[i].x=p[i];
        else t[i].a1=1,t[i].x=p[i]+q[i]-p[i]*q[i]-k;
        if(ld(q[i]-k,0))t[i].a0=0;
        else t[i].a0=1,t[i].x-=(q[i]-k),sum+=q[i]-k;
    }
    sort(t+1,t+1+n,[](node a,node b){return a.x>b.x;});
    for(i=1; i<=a; i++)c+=t[i].a1,sum+=t[i].x;
    for(; i<=n; i++)c+=t[i].a0;
    return c<b;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> a >> b;
    for(int i=1; i<=n; i++) cin >> p[i];
    for(int i=1; i<=n; i++) cin >> q[i];
    double l=0,r=1,v=0;
    while(fabs(r-l)>1e-8)
    {
        double mid=(l+r)/2;
        if(ck(mid))r=mid;
        else l=mid;
    }ck(l);
    cout << fixed << setprecision(5);
    cout << sum+l*b << '\n';
    return 0;
}