【bzoj1024】[SCOI2009]生日快乐

2015.04.22 09:46 Wed | 2次阅读 | 旧日oi | 固定链接 | 源码

Description

windy的生日到了,为了庆祝生日,他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy,一共有 N 个人来分这块大蛋糕,要求每个人必须获得相同面积的蛋糕。 windy主刀,每一切只能平行于一块蛋糕的一边(任意一边),并且必须把这块蛋糕切成两块。这样,要切成 N 块蛋糕,windy必须切 N-1 次。为了使得每块蛋糕看起来漂亮,我们要求 N 块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么?

Input

包含三个整数,X Y N。

Output

包含一个浮点数,保留6位小数。

Sample Input

5 5 5

Sample Output

1.800000

HINT

【数据规模和约定】
100%的数据,满足 1 <= X,Y <= 10000 ; 1 <= N <= 10 。

题解

我用二分答案写的……因为没考虑n=1的情况wa了好久……

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define eps 1e-7
using namespace std;
double x,y,l,r,mid,ans,area;
int n;
bool check(double x,double y,int need)
{
    if(x>y) swap(x,y);
    if(need==1) return y/x<=mid;
    double tmp=0;
    for(int i=1;i<need;i++)
    {
        tmp=i*area;
        if(check(x,tmp/x,i)&&check(x,y-tmp/x,need-i)) return 1;
    }
    for(int i=1;i<need;i++)
    {
        tmp=i*area;
        if(check(y,tmp/y,i)&&check(y,x-tmp/y,need-i)) return 1;
    }
    return 0;
}
int main()
{
    cin>>x>>y>>n;area=x*y/n;
    if(x>y) swap(x,y);
    l=1,r=y/(x/n),ans=r;
    while(r-l>eps)
    {
        mid=(l+r)/2;
        if(check(x,y,n))  ans=mid,r=mid;
        else l=mid;
    }
    printf("%.6lf\n",ans);
}```