解法:深度优先搜索
本质更像是一个分治法
我们用递归去找每种方法的最大值的最小,然后返回就可以。
注意点:
1.分割方式:在x/n或者y/n的整数位置去分割
2.循环时去循环分割位置的块数(或者位置),并且最大就到半数就可以,剩下的一般也是重复的不浪费那个复杂度
#include <bits/stdc++.h>
using namespace std;
const int N = 10100;
int x, y, n;
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 = 10000; // 1
for (int i = 1; i <= n/2; i ++) // 2
{
ans = min(ans, min(max(dfs(x-a*i, y, n-i), dfs(a*i, y, i)), max(dfs(x, y-b*i, n-i), dfs(x, b*i, i))));
}
return ans;
}
int main()
{
cin >> x >> y >> n;
double ans = dfs(x, y, n);
printf("%.6f\n", ans);
return 0;
}