1 问题
有一个由很多木棒构成的集合，每个木棒有对应的长度，请问能否用集合中的这些木棒以某个顺序首尾相连构成一个面积大于 0 的简单多边形且所有木棒都要用上，简单多边形即不会自交的多边形。 初始集合是空的，有两种操作，要么给集合添加一个长度为 L 的木棒，要么删去集合中已经有的某个木棒。每次操作结束后你都需要告知是否能用集合中的这些木棒构成一个简单多边形。
-
输入描述:
每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n 表示操作的数量(1 ≤ n ≤ 50000) ， 接下来有n行，每行第一个整数为操作类型 i (i ∈ {1,2})，第二个整数为一个长度 L(1 ≤ L ≤ 1,000,000,000)。如果 i=1 代表在集合内插入一个长度为 L 的木棒，如果 i=2 代表删去在集合内的一根长度为 L 的木棒。输入数据保证删除时集合中必定存在长度为 L 的木棒，且任意操作后集合都是非空的。 -
输出描述:
对于每一次操作结束有一次输出，如果集合内的木棒可以构成简单多边形，输出 “Yes” ，否则输出 “No”。 -
输入例子:
5
1 1
1 1
1 1
2 1
1 2 -
输出例子:
No
No
Yes
No
No
2 解法
首先，要能够构成一个简单多边形需要满足两个条件：
- 至少有3条边
- 最长边的长度小于其余所有边长度之和
知道以上两点之后，我们很容易的就可以完成这道题目了。Python代码如下：
def solution():
l=[]
n = input('n: ')
for i in xrange(n):
op, data = map(int, raw_input('line %d: ' % (i + 1)).split())
if op == 1:
l.append(data)
else:
l.remove(data)
print 'Yes' if len(l) > 2 and 2 * max(l) < sum(l) else 'No'
但题目中提到的数据量较大，以上的做法效率较低。这道题应该是希望我们可以运用一些合适的数据结构来提高计算的效率。这个数据结构需要需要是有序的，这样我们才可以在插入或者删除后方便的找到最大边的长度，并且插入和删除的复杂度要尽量低。可以想到，能够自平衡的二叉树是个不错的选择，例如AVL树和红黑树，这样的话插入删除和查找均可以在$\log(n)$时间内完成。在Python中，我们可以直接使用bitrees这个库中的树结构。bitrees支持普通的二叉树，AVL树和红黑树三种树结构，并且同时有Python和C的实现。鉴于红黑树往往表现优于AVL树，所以我们选择使用C实现的红黑树。除此之外，树中的节点中以{k:v}的形式表示边的长度和此长度边的条数。具体如下：
import bintrees
def tree_solution():
tree = bintrees.FastRBTree()
sum_ = 0 # 所有边长度总和
len_ =0 # 边的数量
n = input('n: ')
for i in xrange(n):
op, data = map(int, raw_input('line %d: ' % (i + 1)).split())
if op == 1:
if data in tree:
tree[data] += 1
else:
tree[data] = 1
sum_ += data
len_ += 1
else:
if tree[data] == 1:
tree.remove(data)
else:
tree[data]-=1
sum_ -= data
len_ -= 1
print 'Yes' if len_ > 2 and 2 * tree.max_key() < sum_ else 'No'
可惜的是，bitrees这个库不久前已经停止开发了，作者建议需要使用有序数据结构的开发者使用sortedcontainers。Python的标准库中的bisect，heapq和Queue.PriorityQueue常常不能满足开发者对有序数据结构的需求，所以有时就需要第三方的库了，sortedcontainers是众多类似的库中还不错的一个，其具体使用的数据结构和性能表现可以看作者在PyCon 2016上的演讲(YouTube播放)。
Comments