校招真题练习029 圈地运动(360)

圈地运动

圈地运动,就是用很多木棍摆在地上组成一个面积大于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边。

上一篇:029.[转] SSO单点登录的通用架构实现


下一篇:029 函数和代码复用