pythonTip 61 正方形拼接

题目描述： 现在有一堆木棒，告诉你它们的长度，判断能否用这些木棒拼接成正方形。注意：所有的木棒都要用上，且不能截断。给你一个正整数list L, 如 L=[1,1,1,1], L中的每个数字代表一个木棒的长度，如果这些木棒能够拼成一个正方形，输出Yes，否则输出No。如L=[1,1,1,1]，则输出Yes;L=[1,1,1],则输出No。注：数据已于2014-03-11加强，之前通过的代码可能无法再次通过。

示例： 输入：L = [1, 1, 1, 1]

输出：Yes

分析:

如果木棒总长度不是4的倍数，那么肯定不能组合成一个正方形。

如果我们用排列组合的方式，那就相当于是 4^n 次方，肯定超时，就不多想了。

然后我再想，先一分为二，再一分为二。 初步估计了一下时间复杂度，放弃了。

正确的办法：

1. 将所有木棒根据长度从大到小排序。
2. 得到所有木棒的长度总和，判断能否构成四边形以及四边的长度。
3. 再依次将木棒放到四边剩余长度最大的边。
4. 循环操作第3步，直到所有木棒全部放入四边。
5. 最后判断四边是否全部为0。

虽然不知道为啥可以这样，但是代码通过了。我还是给出我的一个思考，感觉没啥问题。

假设我们现在手里拿了 1 根木棒，并且只能放入剩余长度最大的边，其他边放不下这根木棍，那就只能放入剩余长度最大的边了。

如果有 n 个边都可以放，并且这 n 个边剩余长度都一样，那就随便放1个边都可以。

如果现在有 n 个边都可以放，但是 n 个边的 剩余长度都不一样，怎么办？

假设现在有木棒 a > b。 2个边 分别为 A>B。

把 a 放入 A 中，那么A就变成了 A-a。

把 a 放入 B 中，那么B就变成了 B-a

因为 A>B， 所以 A-a > B-a 。

那么 b < A-a 的可能就比 b < B-a 的可能要高，这样我们就可以把更多的木棒加入4边中。

而我们的目的就是尽可能的把所以木棒放入到4个边中。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

sum_L = sum(L)

if sum_L%4  or not sum_L:
    print("No")
else:
    lst = [sum_L//4 for i in range(4)]
    L.sort()
    while L:
        # print(L.pop())
        lst[3] -= L.pop()
        lst.sort()
    if not min(lst):
        print("Yes")
    else:
        print("No")