首页 > 代码库 > HDU 2289 Cup(二分可以,但是除了二分呢?)

HDU 2289 Cup(二分可以,但是除了二分呢?)

这道题目,算数学题吗?算二分题吗?充其量算个水题吧...

首先,没有用二分,但是发现了一种新的解法来代替二分。

若果按照i从0,每次增加0.00000001来一直枚举到h的话,绝逼超时。枚举量太大了

但是可以分成两步来呀:

#include<cstdio>
#include<cmath>
#define pai acos(-1.0)

double r1,r2,h,v;
double get_v(double temp)
{
    double rr=r1+(r2-r1)*temp/h;
    return pai*temp*(r1*r1+rr*rr+r1*rr)/3;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf%lf",&r1,&r2,&h,&v);
        double i;
        for(i=0;i<100;i+=0.0001)
        {
            if(get_v(i)>v)
                break;
        }
        double j;
        for(j=i-0.0001;j<=i;j+=0.00000001)
        {
            if(get_v(j)>v)
                break;
        }
        printf("%.6lf\n",j);
    }
    return 0;
}

虽然时间久了一点,单这道题的数据是可以过得。自己想到方法解决问题,很开心。

下面是迪神一下子就想到的二分解法,说来迪神也真是牛逼……在我们这种菜鸟云集的地方,应该算的上是鹤立鸡群了。。。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
double r,R,H,v,m,x,y;
int L()
{
    if((PI * m * (r*r + r*((R-r)/H*m+r) + ((R-r)/H*m+r)*((R-r)/H*m+r))/3-v)>1e-7) return 1;
    else return 0;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>r>>R>>H>>v;
        x=0,y=H;
        while((y-x)>1e-7)
        {
            m=x+(y-x)/2;
            if(L()) y=m;
            else x=m;
        }
        printf("%.6lf\n",x);
    }
}

就是这个样子,打电话久了会困……原来是真的。。。