圈地运动,就是用很多木棍摆在地上组成一个面积大于0的多边形~
小明喜欢圈地运动,于是他需要去小红店里面买一些木棍,期望圈出一块地来。小红想挑战一下小明,所以给小明设置了一些障碍。障碍分别是:
1.如果小明要买第i块木棍的话,他就必须把前i-1块木棍都买下来。
2.买了的木棍都必须用在圈地运动中。
那么请问小明最少买多少根木棍,才能使得木棍围成的图形是个面积大于0多边形呢?圈地运动,就是用很多木棍摆在地上组成一个面积大于0的多边形~
小明喜欢圈地运动,于是他需要去小红店里面买一些木棍,期望圈出一块地来。小红想挑战一下小明,所以给小明设置了一些障碍。障碍分别是:
1.如果小明要买第i块木棍的话,他就必须把前i-1块木棍都买下来。
2.买了的木棍都必须用在圈地运动中。
那么请问小明最少买多少根木棍,才能使得木棍围成的图形是个面积大于0多边形呢?第一行一个数n,表示木棍个数。
第二行n个数,第i个数表示第i个木棍的长度ai
1<=n<=10000
1<=ai<=10000
输出一个数,表示最少需要的木棍个数,如果无解输出-1
3 6 8 10
3
用三根6,8,10的木棍可以组成一个直角三角形的图形。
var num = readline(); var arr = readline().split(' '); var result = getResult(num,arr); function getResult(num,arr){ //边数大于等于3,且n条边的和减去max大于前n项的最大值max if(num<3) return -1; var sum = parseInt(arr[0])+parseInt(arr[1])+parseInt(arr[2]); var max = Math.max(arr[0],arr[1],arr[2]),flag = false; if(sum-max>max) return 3; for(var i = 3;i<num;i++){ sum +=parseInt(arr[i]); max = Math.max(max,arr[i]); if(sum-max>max){ flag = true; return i+1; break; } } if(!flag) return -1 } console.log(result);
//用的javascript语言 var data = []; while(line = readline()){ data.push(line); } var num = data[0]; newdata = data[1].split(' ').map(a=>parseInt(a)); var result = -1; for(var i = 3;i<=num;i++){ var max = Math.max.apply(this,newdata.slice(0,i)); var str = newdata.slice(0,i); str.splice(newdata.indexOf(max),1); var sum = str.reduce(function(a,b){ return a+b; }); if(sum>max) {result=i;break;} } print(result);