传送门:牛客

题目描述:

windy的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy ，一共有 N 个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。
windy主刀，每一切只能平行于一块蛋糕 的一边（任意一边），并且必须把这块蛋糕切成两块。这样，要切成 N 块蛋糕，windy必须切 N-1 次。
为了使得每块蛋糕看起来漂亮，我们要求 N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么？
输入:
5 5 5
输出:
1.800000

emmm,这是一道分治题??,第一感觉有点像dp,但是dp似乎考虑的方面有亿点点的多,并且众所周知一般这种dp感觉很烦的题目大概率是能使用分治来解决的.比如这道题…但是假设分治想不出来的,这道题就有点难以下手了

主要思路:

1. 既然我们想到了分治,那么久尽量的朝分治来想这道题,我们会发现这道题对于每一块只有两种情况,要么横着切,要么竖着切.因此需要搜索.对于每一个块,我们可以选择一个位置,将其切为左右两块,然后此时假设已经不能再切了,就记录此时我们的答案,假设还能再切就继续的进行搜索.如此进行分治.那么此时最重要的的是如何找出我们可以切的位置,因为我们肯定是不能直接枚举精度来进行分治的.
2. emmm,此时我们需要发现我们的蛋糕的最小长度应该为Y/(N-1),宽度为X/(N-1)假设我们此时Y是大于X的,为什么是这样的一个数值呢.因为我们每一块蛋糕的面积是固定的显然是X*Y/(N-1),所以假设我们的长或者宽小于这个限定值的话,但是我们的长和宽最大只有X或Y,所以此时我们的面积不可能达到我们的所需面积.
3. 并且我们的长度和宽度应该只能是我们的最小限度的整数倍.这一点可能有点难以理解,可以画图来辅助理解.大致情况应该是这样,假设我一个蛋糕的长或宽不是整数倍的话,肯定会导致有一块蛋糕的长或者宽会小于我们的最小限度.因为假设我们的大蛋糕已经被正常的分成了很多个小蛋糕(即最小单位,先不管我们切多少块,反正最后的蛋糕肯定是由这么多个小块合成的),但是每一块最终的小蛋糕肯定是有一块形状和他一样的,因为面积相同,最后肯定至少有一块一模一样的,那么此时假设我的这块蛋糕的长或者宽并不是整数倍,那么必然会有一块蛋糕的长和宽是比我们的最小限度要小的,那么要不这两个蛋糕最后是合在一块的(这样面积又相互补全了),要么就不可能与其他的蛋糕面积相同

这部分感觉不太好讲,请将自行画图结合题解进行理解

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
double x,y,n;
double max(double a,double b) {
	if(a>=b) return a;
	else return b;
}
double min(double a,double b) {
	if(a<=b) return a;
	else return b;
}
double dfs(double xx,double yy,double k) {
	if(k==1) return max(xx,yy)*1.0/min(xx,yy)*1.0;
	double ans=inf;
	double ans1,ans2;
	for(double i=1;i<=k*1.0/2;i++) {
		ans1=max(dfs(i*xx/k,yy,i),dfs(xx-i*xx/k,yy,k-i));
		ans2=max(dfs(xx,i*yy/k,i),dfs(xx,yy-i*yy/k,k-i));
		ans=min(min(ans1,ans2),ans);
	}
	return ans;
}
int main() {
	cin>>x>>y>>n;
	printf("%.6lf\n",dfs(x,y,n));
	return 0;
}