圈地运动
圈地运动,就是用很多木棍摆在地上组成一个面积大于0的多边形~
小明喜欢圈地运动,于是他需要去小红店里面买一些木棍,期望圈出一块地来。小红想挑战一下小明,所以给小明设置了一些障碍。障碍分别是:
1.如果小明要买第i块木棍的话,他就必须把前i-1块木棍都买下来。
2.买了的木棍都必须用在圈地运动中。
那么请问小明最少买多少根木棍,才能使得木棍围成的图形是个面积大于0多边形呢?
输入描述:
第一行一个数n,表示木棍个数。
第二行n个数,第i个数表示第i个木棍的长度ai
1<=n<=10000
1<=ai<=10000
输出描述:
输出一个数,表示最少需要的木棍个数,如果无解输出-1
1 def main(): 2 N = int(input()) 3 if N <= 2: 4 print(-1) 5 else: 6 ary = list(map(int,input().split())) 7 leftpart = ary[0] + ary[1] 8 curmax = max(ary[0],ary[1]) 9 for i in range(2,N): 10 cur = ary[i] 11 if cur >= curmax:#新元素是最大的 12 curmax = cur#更新最大元素 13 if leftpart > cur: 14 print(i+1) 15 return 16 else: 17 leftpart += cur 18 else:#新元素不是最大的 19 #不更新最大元素 20 leftpart -= curmax 21 leftpart += cur 22 if leftpart > curmax: 23 print(i+1) 24 return 25 else: 26 leftpart += curmax 27 print(-1) 28 29 if __name__ == '__main__': 30 main()
算法思路:几何 + 贪心法。
判断是否能组成三角形:最小的两边之和大于第三边。
判断是否能组成四边形:最小的三边之和大于第四边。
……
判断是否能组成N边形,最小的N-1边之和大于第N边。