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