BZOJ

BZOJ 1024 生日快乐

题意

将X*Y的矩形蛋糕平均切成n份，每次只能平行于蛋糕一边切，求蛋糕的长边比短边的最大值最小是多少。

数据范围

$$1\leq X,Y\leq10000\ \ \ ;\ \ \ n\leq10$$

题解

暴搜，枚举切点，假设平行于长切一刀，使整块蛋糕分成i人份和n-i人份，那么切点一定是 X/n*i，因为每人分得蛋糕面积为(X*Y)/n，i人份要求总面积为(X*Y)/n*i。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<iostream>
using namespace std;
double dfs(int n,double x,double y)
{
	double r=1e6;
	if (n==1)
	{
		if (x>y) return x/y;
		return y/x;
	}
	for (int i=1;i*2<=n;i++)
		r=min(r,max(dfs(i,x/n*i,y),dfs(n-i,x-x/n*i,y)));
	for (int i=1;i*2<=n;i++)
		r=min(r,max(dfs(i,x,y/n*i),dfs(n-i,x,y-y/n*i)));
	return r;
}
int main()
{
	int x,y,n;
	scanf("%d%d%d",&x,&y,&n);
	printf("%.6lf\n",dfs(n,x,y));
	return 0;
}