ac1066

经过分析后的二分

题目是

Josnch星球是一个赌博之风盛行的星球。每个人一出生就有一定数额的钱，之后的所有收入只能由赌博获得（OMG,如果RP不好，输光了所有的钱。。。）假设赌博公司的某场赌博有N个结果，每个结果能获得的赔率比分别是a[1],a[2]...a[N]。假设现在XXX有X块钱，问他选择怎样的策略才能使得最坏情况下回报最大（假设N个结果中只有一个是有回报的，X块钱必须全部用在这次赌博上，赔率比就是a[i]，假设你在第 i 个结果中投入了 y 块钱，那么你的回报是 y * a[i]，所谓策略是你在每个结果上的投入应该是怎么分配，比如样例N = 2的时候，赔率比分别是1,2，你有1000块钱，那么买第一个2000 /3,, 后一个1000 / 3，这样最坏情况下你的回报是666.67）

不妨假设最坏情况下回报为mid，假设在每个结果上的投入分别是x[1],x[2]...x[n],那么则有min(x[1] * a[1], x[2] * a[2] .. x[n] * a[n]) >= mid，即对于任意的 i ,有x[i] * a[i] >= mid，所以x[1] >= mid / a[1] x[2] >= mid / a[2] ... x[n] >= mid / a[n]。因为X = x[1] + x[2] + .. x[n] 那么如果mid / a[1] + ... mid / a[n] <= X,说明最坏情况下至少可以取得的回报为mid(每个投入为x[1]...x[n]即可，剩余的钱随便乱搞）。否则说明总钱数不能满足这样情况。因此，如果mid满足条件，即mid / a[1] + ... + mid / a[n] = mid * (1 / a[1] + .. 1 / a[n]) <= X，对于任意P <= mid的数，必然满足P * (1 / a[1] + .. 1 / a[n]) <= X 如果mid不满足条件，那么mid * (1 / a[1] + .. 1 / a[n]) > X,对于任何大于mid的数Q，Q * (1 / a[1] + ... 1 / a[n]) > mid * (1 / a[1] + .. 1 / a[n]) > X。所以mid具有单调性，因此二分mid即可。

上面是大神的解释

感觉是二分能取到的最小值

#include <iostream>

#include<cstdio>

#include<string.h>

using namespace std;

double A[];

int main()

{

    int n;

    while(scanf("%d",&n)==){

        for(int i=;i<n;++i)

          scanf("%lf",&A[i]);

        double X;

        scanf("%lf",&X);

        double L=,R=X*100.0,mid ,ans;

        double eps=1e-;

        while(L+eps<=R){

            mid=(L+R)/;

            double sum=;

            for(int i=;i<n;++i)

                sum+=mid/A[i];

            if(sum<=X){

                ans=mid;

                L=mid+eps;

            }

            else {

                R=mid-eps;

            }

        }

        printf("%.2lf\n",ans);

    }

    return ;

}

巴特西

ac1066

最新文章

热门文章