bzoj 1024 SCOI2009 生日快乐例题

bzoj 1024 SCOI2009 生日快乐题解

转载请注明出处：http://blog.csdn.net/jiangshibiao/article/details/22856919

【原题】

1024: [SCOI2009]生日快乐

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1155 Solved: 802
[Submit][Status]

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<=10，所以果断直接爆搜。我的思路是这样的：每次二分枚举一个值，然后验证。每次验证的时候把一块蛋糕切成两部分（枚举切点）。当蛋糕只有一块的时候判断是否符合要求。

A掉后我去看标解。太神了，它们直接略去二分，然后把我判断时返回的布尔值直接改成最小值。

【代码】

#include<cstdio>
using namespace std;
int n;
double x,y,t,ans;
bool check(double x,double y,double limit,int k)
{
  if (x<y) {t=x;x=y;y=t;}
  if (k==1) {if (x/y<=limit) return true;return false;}
  for (int i=1;i<=k/2;i++)
  {
    double yy=y/double(k)*i;
    if (check(x,yy,limit,i)&&check(x,y-yy,limit,k-i)) return true;
  }
  for (int i=1;i<=k/2;i++)
  {
    double xx=x/double(k)*i;
    if (check(xx,y,limit,i)&&check(x-xx,y,limit,k-i)) return true;
  }
  return false;
}
double erfen(double l,double r)
{
  double mid=(l+r)/2;
  if (r-l<=0.0000001) return mid;
  if (check(x,y,mid,n)) return erfen(l,mid);
  return erfen(mid,r);
}
int main()
{
  scanf("%lf%lf%d",&x,&y,&n);
  if (x<y) {t=x;x=y;y=t;}
  ans=erfen(1,x/(y/double(n)));
  printf("%.6lf",ans);
  return 0;
}

bzoj 1024 SCOI2009 生日快乐 例题