Description
windy 的生日到了, 为了庆祝生日, 他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕. 现在包括 windy, 一共有 N 个人来分这块大蛋糕, 要求每个人必须获得相同面积的蛋糕. windy 主刀, 每一切只能平行于一块蛋糕的一边 (任意一边), 并且必须把这块蛋糕切成两块. 这样, 要切成 N 块蛋糕, windy 必须切 N-1 次. 为了使得每块蛋糕看起来漂亮, 我们要求 N 块蛋糕的长边与短边的比值的最大值最小. 你能帮助 windy 求出这个比值么?
Input
包含三个整数, X Y N.1 <= X,Y <= 10000 ; 1 <= N <= 10
Output
包含一个浮点数, 保留 6 位小数.
- Sample Input
- 5 5 5
- Sample Output
- 1.800000
- Solution
坑人的题目..
一开始以为 \(n=1e4\), 然后 yy 二分 + 爆搜 + 各种可行性剪枝, 推了一大堆约束总觉得不对劲... 然后再看一眼题目发现 \(n\) 只有 \(10\)...
直接爆搜就好了, 只跑了十多毫秒.
- #include<bits/stdc++.h>
- using namespace std;
- void read(int &x) {
- x=0;int f=1;char ch=getchar();
- for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
- for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
- }
- #define write(x) printf("%d\n",x)
- const int maxn = 2e5+10;
- double dfs(int k,double x,double y) {
- if(k==1) return max(x,y)/min(x,y);
- double ans=1e9;
- for(int i=1;i<=(k>>1);i++) ans=min(ans,max(dfs(i,x/k*i,y),dfs(k-i,x/k*(k-i),y)));
- for(int i=1;i<=(k>>1);i++) ans=min(ans,max(dfs(i,x,y/k*i),dfs(k-i,x,y/k*(k-i))));
- return ans;
- }
- int main() {
- int n,x,y;read(x),read(y),read(n);
- printf("%.6lf\n",dfs(n,x,y));
- return 0;
- }
[bzoj1024] [SCOI2009] 生日快乐
来源: http://www.bubuko.com/infodetail-2947929.html