当前位置：首页 > article >正文

3.拼正方形python解法——2024年省赛蓝桥杯真题

article 2025/2/1 6:34:23

问题描述：3.拼正方形 - 蓝桥云课

小蓝正在玩拼图游戏，他有 7385137888721 个 2×2 的方块和 10470245 个 1×1 的方块，他需要从中挑出一些来拼出一个正方形，比如用 3 个 2×2 和 4 个 1×1 的方块可以拼出一个 4×4 的正方形，用 9 个 2×2 的方块可以拼出一个 6×6 的正方形，请问小蓝能拼成的最大的正方形的边长为多少。

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

问题分析

本题较为简单，这里我们选择使用二分搜索作为解决本题的核心算法，已知的条件是：

1，有两种不同数量不同变长的正方形

2，所求最后图形为正方形，但要求其边长最大

从数学角度分析，设正方形的边长为 n，则它的总面积为 $n^2$ ，由于一个 2×2 的方块占 4 个单位面积，因此可优先使用 2×2 的方块，设使用了 x 个 2×2 的方块，它们的总面积为 4x 。

剩余需要用 1×1 方块补充的面积为 $n^2 - 4x$ ，这个值不能超过 1×1 方块的数量。

目的便是：找到最大的 n，使得：

$n^2 <=$ 边长为2的方块提供的面积 + 边长为1的方块提供的面积

即：

$n^2 <= 7385137888721*4 + 10470245*1$

以上便是本题比较直观的数学语言表示，到这里我们不妨做一个比较极端的假设：

假设均使用 2x2 的方块堆叠成最终的这样一个正方形，则用上的2x2方块的最少数量应当是：

$min(7385137888721, n^2//4)$

为这部分值赋予变量名：used_two_by_two

此时我们再将所有已用的 2x2 正方形假设成为4个 1x1 的正方形叠加而成，为了达到最终的最大正方形的效果，则现在应当做的是，使用足够数量的 1x1 的正方形去填补剩下的可能存在的“空隙”，示意图如下：其中绿色部分为可能需要使用 1x1 的正方形去填补的部分

记 1x1 的正方形填补的部分为 remaining_area，则这部分的数量应该为：

$remaining\_area = n^2 - 4 * used\_two\_by\_two$

接下来我们应该做的事情就是：判断 remaining_area 是否小于等于 1×1 方块的总数。本条件也是二分搜索进行的核心

总的逻辑分析如上，既然确定使用二分搜索，那对什么元素进行搜索呢？这里毫无疑问是正方形的边长了，那搜索的范围应该是什么呢？二分搜索嘛，你知道的呀，二分搜索的时间复杂度嘛，你知道的呀

因此，我们同样假设两个极端，首先由题可知，最小的能拼成的正方形为边长 1x1 的正方形，则二分搜索的左边界为1；其次，我们假设所有的小正方形均被用上，则最后的大正方形，其面积为： $7385137888721*4 + 10470245*1$ ，那么其可能的最大边长则是： $int(\sqrt{(7385137888721*4 + 10470245*1)})$

到此，二分搜索的左边界与右边界都确定的了，接下来就是编程时间！

代码描述

由于二分搜索的代码实现起来比较简单，所以这里不对代码做额外的详细讲解了，有需要的同学可以评论区或者私信留言，这里需要注意的是，二分搜索的退出条件，应当着重考虑实际需要的1x1的正方形数量和题中所给的最多的正方形数量

代码如下：

def max_square_side():
    max_two_by_two = 7385137888721  # 2×2 方块数量
    max_one_by_one = 10470245       # 1×1 方块数量

    # 设定合理的二分查找范围
    left, right = 1, int((max_two_by_two * 4 + max_one_by_one) ** 0.5)

    while left < right:
        mid = (left + right + 1) // 2  # 取上中位数，防止死循环
        total_area = mid * mid  # 需要填充的总面积

        # 计算最多能使用的 2×2 方块数量
        max_used_two_by_two = min(max_two_by_two, total_area // 4)
        remaining_area = total_area - max_used_two_by_two * 4  # 需要补充的 1×1 方块面积

        if remaining_area < max_one_by_one:
            left = mid  # 继续尝试更大的 n
        elif remaining_area == max_one_by_one:
            return left
        else:
            right = mid - 1  # n 太大了，尝试更小的 n

    return left  # 返回最大合法的 n

print(max_square_side())  # 输出最大边长

本地运行结果：