题目陈述

大意：给定两种若干数量的蛋糕和一些盘子，问所有的分法中，蛋糕数量最少的盘子中分到最多的蛋糕数量是多少。所有分法应该满足：同一个盘子不装有两种蛋糕、每个盘子都有蛋糕。

算法一：朴素做法

算法思路

  • 为了不多次重复冗余的文字，接下来我们约定，将蛋糕数量最少的盘子中分到最多的蛋糕数量称为。
  • 我们先这样分析，如果有个盘子，只有一种蛋糕，数量为，那么所有分法的就是
  • 为什么？此处我们感性理解一下，取的时候，一定是所有盘子的最大值和最小值的差值是最小的，如果不是最小的，将最大值的几个蛋糕，移动到最小值上面，我们又得到了更大的，与我们当初的定义相互矛盾。
  • 我们从依次一个位置一个位置放蛋糕，循环的放置，直至放完位置，这样放置出来的必然是最优情况，此时最大值和最小值的差值至多为，将最大值上面的一个移动到最小值，则完成了互换，即此时最大值和最小值的差值稳定，即无法减小，即最大值和最小值的差值是最小的
  • 这种情况，即我们计算有个盘子，只有一种蛋糕，数量为，的，按照上面的分法，只需要即可计算出来
  • 那么两种蛋糕如何处理？同理，枚举第一种蛋糕用的盘子，剩下的种盘子给第二种蛋糕，二者各自的再取一个最小值，即可得到该分法的
  • 线性遍历即可获取所有方案
  • 此处可能有同学想问，是否存在只用一种蛋糕就得到了所有分法的?因为题目数据保证了，故不存在只有一种蛋糕分法而得到所有分法的的情况。

代码实现

class Solution
{
public:
    int splitCake(int n, int a, int b)
    {
        int aAns, bAns, ans = -1;
        //第一种单独的ans，第二种单独的ans，总的ans
        for (int i = 1; i < n; i ++) 
        {
            aAns = a / i; //求解第一种的ans
            bAns = b / (n - i); //求解总的ans 
            if(aAns > 0 && bAns > 0) //两种单独的方法都合法
                ans = max(ans, min(aAns, bAns)); //求解总得ans
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度，一个for循环从，复杂度为
  • 空间复杂度，定义了变量，复杂度为

算法二：二分法

  • 我们设一种分法中第一种、第二种蛋糕分别占用了个盘子，每个盘子内的蛋糕数量分别为
  • 则有
  • 且，所以则有，
  • 故有
  • 故同理有
  • 显然最后的会取二者中更小的一个，即
  • 若方案合法则有
  • 即
  • 易得
  • 即
  • 假设此处的我们用来枚举，我们可以知道对于答案有这样一个性质，都是合法方案，都不合法，如图

图片说明

  • 对于前者（其实题目没有说一定需要放完所有蛋糕），我们将最小值的位置移动一块到最大值的位置即可构造更小的情况
  • 对于后者，反证法，如果合法，则与已有条件矛盾，故得证。
  • 即区间具有二段性，可以使用二分法。
  • 此时我们对进行二分答案即可

    代码实现

    class Solution
{
public:
  int splitCake(int n, int a, int b)
  {
      int l = 1, r = min(a, b), mid; //左边界，右边界，中点
      ////当a<b,a中无法拿出b个蛋糕来，反之亦然，故右边界需要取小的那个
      while (l < r) //l == r的时候，代表已经找出答案
      {
          mid = (l + r + 1) / 2; //向上取整，避免死循环
          if (check(n, a, b, mid)) //该分法合法，说明可以取更大的值
              l = mid; //左边界缩小
          else //该分法不合法，说明只能取最小的值
              r = mid - 1; //右边界缩小
      }
      return l; //返回答案
  }
  bool check(int &n, int &a, int &b, int x) //二分条件
  {
      return a / x + b / x >= n; //两种蛋糕每盘都分最小的，若合法总和应该不小于n
  }
};

复杂度分析

  • 时间复杂度，为二分答案的复杂度，最多二分次，复杂度为
  • 空间复杂度，定义了，为