题目描述: 现在有一堆木棒,告诉你它们的长度,判断能否用这些木棒拼接成正方形。注意:所有的木棒都要用上,且不能截断。给你一个正整数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 次方,肯定超时,就不多想了。
然后我再想,先一分为二,再一分为二。 初步估计了一下时间复杂度,放弃了。
正确的办法:
- 将所有木棒根据长度从大到小排序。
- 得到所有木棒的长度总和,判断能否构成四边形以及四边的长度。
- 再依次将木棒放到四边剩余长度最大的边。
- 循环操作第3步,直到所有木棒全部放入四边。
- 最后判断四边是否全部为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")