1026 [SCOI2009]生日快乐 dfs
2022/7/4 6:21:44
本文主要是介绍1026 [SCOI2009]生日快乐 dfs,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
链接:https://ac.nowcoder.com/acm/contest/23156/1026
来源:牛客网
题目描述
windy的生日到了,为了庆祝生日,他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy ,一共有 N 个人来分这块大蛋糕,要求每个人必须获得相同面积的蛋糕。 windy主刀,每一切只能平行于一块蛋糕 的一边(任意一边),并且必须把这块蛋糕切成两块。这样,要切成 N 块蛋糕,windy必须切 N-1 次。 为了使得每块蛋糕看起来漂亮,我们要求 N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么?输入描述:
包含三个整数,X Y N。 ≤ X,Y ≤ 10000 ; 1 ≤ N ≤ 10
输出描述:
包含一个浮点数,保留6位小数。示例1
输入
复制5 5 5
输出
复制1.800000
备注:
100%的数据,满足1≤X,Y≤10000;1≤N≤101 \le X,Y \le 10000 ; 1 \le N \le 101≤X,Y≤10000;1≤N≤10 。
分析
二分,贪心,搜索。。
就搜索能用了,二分也分不出啥,这题数据量小。。
其实拿到题,完全不会写。。。我的第一思维好像是贪心,
然后看了雨巨。。手把手教搜索,是真的贴心
切蛋糕嘛,就就直接切。。
然后有个关键,必须切x/n,y/n的倍数的量,直接枚举这个量。然后当切到最后一个的时候计算一下y/x。
dfs(x,y,n)表示当前切的蛋糕的长,宽,需要切的数量
int dy[] = {1,0,-1,0,1,1,-1,-1};
int dx[] = {0,1,0,-1,1,-1,1,-1};
/*文档区
*/
//-------------------------代码----------------------------
//#define int LL
const int N = 1e5+10;
int x,y,n,m;
double dfs(double x,double y,int n) {
if(n == 1) {
return max(x,y) / min(x,y);
}
double a = x / n,b = y / n,ans = 0x3f3f3f3f;
for(int i = 1;i <= n / 2;i++) {
ans = min(ans, min(max(dfs(i * a, y, i), dfs(x - i * a, y, n - i)), max(dfs(x, i * b, i), dfs(x, y - i * b, n - i)))); }
return ans ;
}
void solve()
{
cin>>x>>y>>n;
// V<V<int>>mp(n+1,V<int>(m+1));
printf("%.6lf\n",dfs(x,y,n));
}
signed main(){
clapping();TLE;
// int t;cin>>t;while(t -- )
solve();
// {solve(); }
return 0;
}
/*样例区
*/
//------------------------------------------------------------
这篇关于1026 [SCOI2009]生日快乐 dfs的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享