【20190812】【校招笔试题】圈地运动_360

问题

圈地运动，就是用很多木棍摆在地上组成一个面积大于0的多边形。

小明喜欢圈地运动，于是他需要去小红店里面买一些木棍，期望圈出一块地来。小红想挑战一下小明，所以给小明设置了一些障碍。障碍分别是：

1. 如果小明要买第i块木棍的话，他就必须把前i-1块木棍都买下来。

2. 买了的木棍都必须用在圈地运动中。

那么请问小明最少买多少根木棍，才能使得木棍围成的图形是个面积大于0多边形呢？

输入描述：

第一行一个数n，表示木棍个数。

第二行n个数，第i个数表示第i个木棍的长度ai

1<=n<=10000

1<=ai<=10000

输出描述：

输出一个数，表示最少需要的木棍个数，如果无解输出-1

输入例子1：

3

6 8 10

输出例子1：

3

例子说明1：

用三根6，8，10的木棍可以组成一个直角三角形的图形。

思路及解答

# 构成 N 边形的条件是，任意 N-1 条边之和大于第 N 条边。
n = int(input())
ai = list(map(int, input().split()))
l = len(ai)
result = -1
for i in range(2, l):
    tmp = []
    tmp = ai[0:i+1]
#    tmp.sort()
#    if sum(tmp[: len(tmp)-1]) > tmp[len(tmp)-1]:   # 较小的 N-1 条边之和大于最大的那条边。
    if sum(tmp) > 2*max(tmp):       # 等价的条件是：所有边长度之和大于最大那条边长度的二倍。
        result = i + 1
        break
print(result)
           

知识点

1. 构成 N 边形的条件：任意 N-1 条边之和大于第 N 条边；即所有边之和大于最长的那条边长度的二倍。

（参考：多边形构成问题）