深圳罗湖高端网站建设,宝安医院网站建设,公司网站开发费用怎么做账,asp网站建设公司【每日一题】7月15日题目精讲—生日快乐
[SCOI2009]生日快乐
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K
64bit IO Format: %lld题目描述 windy的生日到了#xff0c;为了庆祝生日#xff0c;他的朋友…【每日一题】7月15日题目精讲—生日快乐
[SCOI2009]生日快乐
时间限制C/C 1秒其他语言2秒
空间限制C/C 262144K其他语言524288K
64bit IO Format: %lld题目描述 windy的生日到了为了庆祝生日他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy 一共有 N 个人来分这块大蛋糕要求每个人必须获得相同面积的蛋糕。 windy主刀每一切只能平行于一块蛋糕 的一边任意一边并且必须把这块蛋糕切成两块。这样要切成 N 块蛋糕windy必须切 N-1 次。 为了使得每块蛋糕看起来漂亮我们要求 N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么 输入描述: 包含三个整数X Y N。 1 ≤ X,Y ≤ 10000 1 ≤ N ≤ 10 输出描述: 包含一个浮点数保留6位小数。 示例1 输入 复制
5 5 5输出 复制
1.800000题解
一看题目最大值最小没错就是二分 一看数据n10,用啥二分。。暴力完事儿了 我们每次切一刀一刀必须平行边 对于要切n刀的xy的蛋糕我们可以在(ix/n)的位置切一刀也可以在iy/n的位置切一刀 ix/n的位置切一刀后左边还需要切i次右边还要切n-i次 可以这么理解每次递归就是砍一刀每次分成上下左右切当切到最后一块就算结束
代码
#includebits/stdc.h
using namespace std;
const int maxn1e47;
double dfs(double x,double y,double k)
{if(k1)return max(x,y)/min(x,y);double resmaxn;for(int i1;ik;i){resmin(res,max(dfs(x/k*i,y,i),dfs(x/k*(k-i),y,k-i)));resmin(res,max(dfs(x,y/k*i,i),dfs(x,y/k*(k-i),k-i)));}return res;
}
int main()
{int x,y,n;cinxyn;printf(%.6lf,dfs(x,y,n));
}
