【每日一題】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

題解：

一看題目，最大值最小，沒錯就是二分
一看數據n<=10,用啥二分。。暴力完事兒了
我們每次切一刀，一刀必須平行邊
對于要切n刀的xy的蛋糕，我們可以在(ix/n)的位置切一刀，也可以在（iy/n）的位置切一刀，
ix/n的位置切一刀后，左邊還需要切i次，右邊還要切n-i次
可以這么理解，每次遞歸就是砍一刀，每次分成上下左右切，當切到最后一塊就算結束

代碼：

#include<bits/stdc++.h> using namespace std; const int maxn=1e4+7; double dfs(double x,double y,double k) {if(k==1)return max(x,y)/min(x,y);double res=maxn;for(int i=1;i<k;i++){res=min(res,max(dfs(x/k*i,y,i),dfs(x/k*(k-i),y,k-i)));res=min(res,max(dfs(x,y/k*i,i),dfs(x,y/k*(k-i),k-i)));}return res; } int main() {int x,y,n;cin>>x>>y>>n;printf("%.6lf",dfs(x,y,n)); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【每日一题】7月15日题目精讲—生日快乐的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。