LeetCode-Day48

生日快乐

一块大小为X * Y的矩形蛋糕，现要将其切成n块面积相同的蛋糕，且每次切的时候只能将。每一切只能平行于一块蛋糕的一边，并且必须切成两块。这样要切成n块需要切n-1刀。要求 N 块蛋糕的长边与短边的比值的最大值最小。求这个比值

思路：这个题目我想了一会儿思路…

一个蛋糕必须切成两块，这个很明显提示我们这个问题需要递归，一个蛋糕变成两个蛋糕的问题。

所以，假设一个蛋糕需要被分成n块，那么第一刀会将这个蛋糕分成两块，带下分别为$i, n - i$，切得方式有两种，一种是将蛋糕分成左右两块，一种是将蛋糕分成上下两块，注意这两种情况是不一样的。然后分别得到这两种切分蛋糕方式所得到的每一块蛋糕长边比上短边的最大值，然后取较小值返回。边界条件就是当$n = 1$的时候，不用切蛋糕，直接返回长边比上短边的值即可。

#include <iostream>
#include <cstdio>
using namespace std;
int X, Y, N;
double max_rate = 0.0;
double min_rate = 1.0e9;

double solve(double x, double y, int n) {
    if(n == 1) {
        if(x < y) {
            swap(x, y);
        }
        return x / y;
    }
    double max_size = 1.0e9;
    for(int i = 1; i <= (n >> 1); i++) {
        // 这i份蛋糕可以位于这个矩阵的上半部分，或者这个矩阵的下半部分
        // 上半部分
        double upper = y / n * i;
        double temp1 =  max(solve(x, upper, i), solve(x, y - upper, n - i));

        double left = x / n * i;
        double temp2 = max(solve(left, y, i), solve(x - left, y, n - i));
        // cout << "temp1 = " << temp1 << " temp2 = " << temp2 << endl;
        max_size = min(max_size, min(temp1, temp2));
    }
    return max_size;
}

int main() {
    while(scanf("%d%d%d", &X, &Y, &N) != EOF) {
        double res = solve((double)X, (double)Y, N);
        printf("%.6f\n", res);
    }
}