SCOI2009 生日快乐

题目大意:n*m的矩形，切成面积相等的n块，要求N 块的长边与短边的比值的最大值最小。n<=10.

初看这道题没有思路，虽然n<=10但是又没说只能切成整数，所以就不知道怎么捉。。二分答案又没想到怎么验证。

事实上，我没有注意到面积相等这个条件。由于只能切（不能拼），所以每次切完的面积必然是n的整数倍，这样就可以搜了。

※注意

double r;
int n=5;
r=1/n;

printf("lf",r);//此时输出0.000000

r=(double)1/(double)n;
printf("%lf",r);//此时输出0.200000

View Code

 1 /**************************************************************
 2     Problem: 1024
 3     Language: C++
 4     Result: Accepted
 5     Time:676 ms
 6     Memory:804 kb
 7 ****************************************************************/
 8  
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cmath>
12 #include <algorithm>
13 #define bigger(a,b) ((a)>(b)?(a):(b))
14 #define minner(a,b) ((a)<(b)?(a):(b))
15 #define INF 999999999;
16 double x,y;
17 int n;
18 double ans;
19 double dfs(double x,double y,int n)
20 {
21     int i;
22     double r,ans=INF;
23     double rtn=bigger(x,y)/minner(x,y);
24     //printf("-------%lf %lf %d %lf\n",x,y,n,rtn);
25     if(n==1) return rtn;
26     r=(double)1/(double)n;
27     for (i=1;i<n;i++)
28     {
29         double a,b;
30         a=bigger(dfs(x*i*r,y,i),dfs(x*(n-i)*r,y,n-i));
31         b=bigger(dfs(x,y*i*r,i),dfs(x,y*(n-i)*r,n-i));
32         ans=minner(ans,minner(a,b));
33     }
34     return ans;
35 }
36 int main()
37 {
38     scanf("%lf%lf%d",&x,&y,&n);
39     double ans=dfs(x,y,n);
40     printf("%lf",ans);
41     return 0;
42 }