题目链接

题解

抓住个数的期望即为概率之和

使用\(A\)的期望为\(p[i]\)

使用\(B\)的期望为\(u[i]\)

都使用的期望为\(p[i] + u[i] - u[i]p[i]\)

当然是用越多越好

但是他很烦地给了个上限，我们就需要作出选择了

有一个很明显的\(O(n^3)\)的\(dp\)，显然过不了

但我们有一个很好的\(WQS\)二分

我们非常想去掉这个上限

那就去掉吧，但是每用一次都要付出一个代价

我们二分这个代价，当使用次数恰好为为\(a\)和\(b\)时就是答案

再加回付出的代价即可

非常巧妙地变成了\(O(n\log^2n)\)

这种二分技巧非常棒

当我们求的东西有一个限制个数时，可以通过设置代价去掉上限

//Mychael#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #define LL long long int#define REP(i,n) for (int i = 1; i <= (n); i++)#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define cls(s,v) memset(s,v,sizeof(s))#define mp(a,b) make_pair
             
              (a,b)#define cp pair
              
               #define eps 1e-9using namespace std;const int maxn = 2005,maxm = 100005,INF = 0x3f3f3f3f;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();} while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();} return flag ? out : -out;}int n,a,b,cnta,cntb;double p[maxn],u[maxn],A,B,ans;int work(double cost){ A = cost; cnta = cntb = 0; ans = 0; int sol; double val; REP(i,n){ val = 0; sol = 0; if (p[i] - A > val) sol = 1,val = p[i] - A; if (u[i] - B > val) sol = 2,val = u[i] - B; if (p[i] + u[i] - u[i] * p[i] - A - B > val) sol = 3,val = p[i] + u[i] - u[i] * p[i] - A - B; if (sol == 1 || sol == 3) cnta++; if (sol == 2 || sol == 3) cntb++; ans += val; } return cnta;}int check(double cost){ B = cost; double l = 0,r = 1.0,mid; while (r - l > eps){ mid = (l + r) / 2.0; if (work(mid) <= a) r = mid; else l = mid; } work(r); A = l; return cntb;}int main(){ n = read(); a = read(); b = read(); REP(i,n) scanf("%lf",&p[i]); REP(i,n) scanf("%lf",&u[i]); double l = 0,r = 1.0,mid; while (r - l > eps){ mid = (l + r) / 2.0; if (check(mid) <= b) r = mid; else l = mid; } check(r); printf("%.8lf",ans + a * A + b * B); return 0;}