首页 > 试题广场 >

圈地运动

[编程题]圈地运动

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

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

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

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

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

第一行一个数n，表示木棍个数。
第二行n个数，第i个数表示第i个木棍的长度ai
1<=n<=10000
1<=ai<=10000

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

示例1

输入

3
6 8 10

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

算法知识视频讲解

张云超

发表于 2019-08-10 15:17:22

1. 思路（1）最重要的一点：构成多边形的条件：其他边之和大于最长边边数大于3 （2）根据题目要求可知，依次检索，达到条件就输出，时间复杂度O（n）（3）第i个点与前i-1个点，只有和的关系（其实是减去最大值的和），所以不需要。 2.在循环读入时所要记录的数据前i项和sum 展开全文

不摸了

发表于 2019-07-30 15:49:15

import java.util.Scanner; public class Main{ public static void main (String[]args){ Scanner in=new Scanner( 展开全文

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师 2019 360集团 Java工程师

上传者：小小

难度：

26条回答 45收藏 7790浏览

圈地运动

扫一扫，把题目装进口袋