Leetcode打卡：切蛋糕的最小总开销I

执行结果：通过

题目 3218 切蛋糕的最小总开销I

有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。

给你整数 m ，n 和两个数组：

• horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。
• verticalCut 的大小为 n - 1 ，其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。

一次操作中，你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一：

1. 沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。
2. 沿着垂直线 j 切开蛋糕，开销为 verticalCut[j] 。

每次操作后，这块蛋糕都被切成两个独立的小蛋糕。

每次操作的开销都为最开始对应切割线的开销，并且不会改变。

请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。

示例 1：

输入：m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

输出：13

解释：

• 沿着垂直线 0 切开蛋糕，开销为 5 。
• 沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
• 沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
• 沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。
• 沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。

总开销为 5 + 1 + 1 + 3 + 3 = 13 。

示例 2：

输入：m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

输出：15

解释：

• 沿着水平线 0 切开蛋糕，开销为 7 。
• 沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。
• 沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。

总开销为 7 + 4 + 4 = 15 。

提示：

• 1 <= m, n <= 20
• horizontalCut.length == m - 1
• verticalCut.length == n - 1
• 1 <= horizontalCut[i], verticalCut[i] <= 103

代码以及解题思路

代码

int cmp(const void * a, const void * b) {
    return * (int *) b - * (int *) a;
}

int minimumCost(int m, int n, int* horizontalCut, int horizontalCutSize, int* verticalCut, int verticalCutSize) {
    qsort(horizontalCut, horizontalCutSize, sizeof(int), cmp);
    qsort(verticalCut  , verticalCutSize  , sizeof(int), cmp);
    int i = 0, j = 0, ans = 0;
    while (i < horizontalCutSize && j < verticalCutSize) 
        ans += horizontalCut[i] > verticalCut[j] ? horizontalCut[i ++] * (j + 1) : verticalCut[j ++] * (i + 1);
    while (i < horizontalCutSize) ans += horizontalCut[i ++] * n;
    while (j <   verticalCutSize) ans +=   verticalCut[j ++] * m;
    return ans;

}

解题思路：

1. 排序切割线：
   • 使用 qsort 函数对 horizontalCut 和 verticalCut 数组进行排序。这里自定义的比较函数 cmp 实现了降序排序（从大到小），因为切割线的位置越大，表示离边缘越远，通常意味着更高的成本。
   • 排序是为了便于后续计算最小成本，因为这样可以保证在遍历切割线时，每次遇到的最大切割线（即成本最高的切割线）都是当前遍历到的最远的切割线。
2. 计算最小成本：
   • 初始化两个指针 i 和 j 分别用于遍历 horizontalCut 和 verticalCut 数组。
   • 初始化变量 ans 用于存储最小成本。
   • 使用一个 while 循环，直到任一指针遍历完其对应的切割线数组。在每次迭代中，比较当前 horizontalCut[i] 和 verticalCut[j] 的值：
     • 如果 horizontalCut[i] 更大，表示当前最大的水平切割线更远，因此应该首先进行这条水平切割。由于此时所有的垂直切割线都在这条水平切割线下方，所以这条水平切割线会将下方的所有小矩形都分割一次，成本为 horizontalCut[i] * (j + 1)（因为已经有 j + 1 条垂直切割线）。
     • 如果 verticalCut[j] 更大，同理，应该首先进行垂直切割，成本为 verticalCut[j] * (i + 1)。
   • 更新 i 或 j 指针，以继续遍历剩余的切割线。
   • 当任一指针遍历完其数组后，剩余未处理的切割线（无论是水平还是垂直）都将直接切割到蛋糕的另一边缘。因此，对于剩余的 horizontalCut 中的切割线，每条的成本为 horizontalCut[i] * n（因为每条水平线都会切割整个宽度 n）；对于剩余的 verticalCut 中的切割线，每条的成本为 verticalCut[j] * m（因为每条垂直线都会切割整个高度 m）。
3. 返回最小成本：
   • 循环结束后，ans 存储了将蛋糕切割成小块的最小成本，返回这个值。

原文地址：https://blog.csdn.net/m0_69493801/article/details/144707835

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！