首页 > 试题广场 > 圈地运动
[编程题]圈地运动

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

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

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

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

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

输入描述:
第一行一个数n,表示木棍个数。
第二行n个数,第i个数表示第i个木棍的长度ai
1<=n<=10000
1<=ai<=10000


输出描述:
输出一个数,表示最少需要的木棍个数,如果无解输出-1
示例1

输入

3
6 8 10

输出

3

说明

用三根6,8,10的木棍可以组成一个直角三角形的图形。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class  {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 木棍的个数
        int n = scanner.nextInt();
        if(n < 3){
            System.out.println(-1);
        }
        List<Integer> lengths = new ArrayList<>();
        for (int i=0;i<n;i++){
            int length = scanner.nextInt();
            lengths.add(length);
        }

        for(int i=2;i<lengths.size();i++){
            int sum = 0;
            int max = 0;
            for(int j=0;j<=i;j++){
                if(lengths.get(j) > max){
                    sum = sum + max;
                    max = lengths.get(j);
                }else{
                    sum = sum + lengths.get(j);
                }

            }
            if(max < sum){
                System.out.println(i+1);
                break;
            }else if(i== lengths.size()-1){
                System.out.println(-1);
            }
        }


    }


}

发表于 2019-08-05 19:11:11 回复(0)
# 思路是n-1边的和大于最长边,就能组成封闭多边形;
while 1:
    try:
        nums = int(input())
        lists = list(map(int, input().strip().split(' ')))
        if nums <= 2:
            print('-1')
            exit()
        index = 2
        for i in range(nums-2):
            # 因为在前面的sum中,把最长边也加进去了,所以后面的max要乘2;
            result = sum(lists[:index+1]) - max(lists[:index+1])*2
            if result > 0:
                print(index+1)
                exit()
            index += 1
        print('-1')
    except:
        break

编辑于 2019-08-13 19:38:21 回复(8)
#coding:utf-8
n = int(input())
nums = list(map(int,input().split()))
for i in range( 2,len(nums)+1):
    lis = nums[0:i]
    suml = sum(lis)
    maxl = max(lis)
    suml = suml - maxl
    if suml > maxl:
        print(i)
        exit()
print("-1")

发表于 2019-08-14 17:22:26 回复(0)
n = int(input())
l = list(map(int,input().split()))

for i in range(2,n):
    a = max(l[:i+1])
    b = sum(l[:i+1]) - a
    if b - a <= 0:
        if i == n -1:
            print(-1)
            break
        continue
    else:
        print(i+1)
        break

发表于 2019-08-17 12:33:55 回复(0)
//用的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);

编辑于 2019-08-28 13:14:32 回复(0)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void change( int &x, int &y, int &z,const int &w){//将最短、次短、最长的棍子依次负值给x,y,z;
    vector<int> rr;
    rr.push_back(x);rr.push_back(y);rr.push_back(z);rr.push_back(w);
    sort(rr.begin(),rr.end());
    z=rr[3];y=rr[2];x=rr[0]+rr[1];
    rr.clear();
    rr.push_back(x);rr.push_back(y);rr.push_back(z);
    sort(rr.begin(),rr.end());
    z=rr[2];y=rr[1];x=rr[0];
}
int main()
{
    int n;
    cin>>n;
    int gs[n];
    for(int i=0;i<n;i++)cin>>gs[i];
    int x=gs[0],y=gs[1],z=gs[2],w=0,r=3;
    for(int i=3;i<n;i++){
        change(x,y,z,w);
    if((x+y<=z)||(z-x>=y)||(z-y>=x))//不满足三角形,将下一根棍子加入
    {w=gs[i];r++;}
        if((x+y>z)||(z-x<y)||(z-y<x)){//满足三角形,退出
            break;
        }
    if(i==n-1)r=-1;
    }
    cout<<r;
    return 0;
}

发表于 2019-08-14 11:24:12 回复(0)
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int NumOfStick = 0; //木棍个数
    cin >> NumOfStick;
    int *a = new int[NumOfStick]();
    for (int i = 0; i < NumOfStick; i++)
    {
        cin >> a[i];
    }
    
    int Max_line = a[0] > a[1] ? a[0] : a[1];
    int Sum = a[0] + a[1];
    int flag = 0;
    for (int d = 2; d <= NumOfStick; d++)
    {
        if (a[d] > Max_line) //更新最大的边
        {
            Max_line = a[d];
        }
        Sum += a[d]; //前d根边的所有和
        if (Sum - Max_line > Max_line)
        {
            cout << d + 1 << endl;
            flag = 1;
            return 0;
        }
    }
    if (flag == 0)
    {
        cout << -1 << endl;
    }

    delete []a;
    return 0;
}

编辑于 2019-08-25 09:50:00 回复(2)
思路:
n-1边的和大于最长边,就能组成封闭多边形
JAVA代码:
import java.util.Arrays;
import java.util.Scanner;

public class 圈地问题 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        int res = angleEnable(nums);
        System.out.println(res);

    }


    public static int angleEnable(int[] nums) {
        //如果边长<2,肯定不能实现
        if (nums == null || nums.length <= 2) return -1;


        //条件: n-1边的和大于最长边,就能组成封闭多边形
        
        int sum = 0; //前N个数之和
        int max = 0;//前N个树中的最大值
        for (int i = 0; i < nums.length ; i++) {
            sum += nums[i];
            max = max > nums[i] ? max : nums[i];
           //如果i > 1(如果不大于1,说明只有2条边,无论如何都构成不了的)
           //并且sum - max > max,即前N个中不含Max的值之和大于Max,说明找到了,直接返回
            //这个注意 + 1 ,因为i从0开始
            if (i > 1 && sum > 2 * max) return i + 1;
        }
                //遍历完所有都不存在则说明不存在
        return -1;
    }

}


编辑于 2019-09-17 11:59:53 回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    int num = 0;
    vector<int> bian;
    int temp = 0;
    int max_bian = 0, add_bian = 0;
    cin >> num;
    for (int i = 0; i < num; i++)
    {
        cin >> temp;
        bian.push_back(temp);
    }  
    for (int j = 0; j < bian.size(); j++)
    {
        if(max_bian < bian[j])
            max_bian = bian[j];
        add_bian = add_bian + bian[j];
        if ((add_bian - max_bian) > max_bian)
        {
            cout << j+1 << endl;
            break;
        }
        if(j == bian.size()-1)
        {
            cout << -1 << endl;
            break;
        }
    }
    return 0;
}
发表于 2019-09-05 22:00:28 回复(0)
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(solution(n, in));
    }
    /*
    题意:输入一组数据,判断前i个数据是否能够构成多边形
    如果输入的数组长度小于2肯定是不能够构成多边形的
    在i>=3的条件下,如果数组前i个数的和sum减去前i个数的最大值max剩余的总和大于sum,即,sum-max>max;
    则可以构成多边形,否者不可以。
    */
    public static int solution(int q, Scanner in) {
        int[] stick = new int[10005];
        int i;
        for (i = 0; i < q; i++) {
            stick[i] = in.nextInt();
        }
        if (q <= 2) {
            return -1;
        } else {
            int sum = stick[0];
            int max = stick[0];
            for (i = 1; i < q; i++) {
                max = Math.max(max, stick[i]);
                sum += stick[i];
                if (i >= 2 && max < (sum - max)) {
                    return i + 1;
                }
            }
            return -1;
        }
    }
}

发表于 2019-08-24 11:45:07 回复(0)
Python版本
n = int(input())
nums = [int(x) for x in input().split()]
for i in range(2,n):
    total = sum(nums[0:(i+1)])
    maxi = max(nums[0:(i+1)])
    minus = total - maxi*2
    if minus > 0:
        result = i + 1
        break 

try:
    print(result)
except:
    print("-1")


发表于 2019-08-15 16:26:47 回复(0)
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);

发表于 2019-08-15 10:18:30 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.print(quandi(sc,n));
    }
    public static long quandi(Scanner sc,int n){
        if(n<3) 
            return -1;
        else{
            long[] arr = new long[n];
            for(int i=0;i<n;i++){
                arr[i]=sc.nextLong();
            }
            long other_sides=0;
            long max=0;
            for(int i=0;i<n;i++){
                if(max<arr[i]){
                    other_sides+=max;
                    max=arr[i];
                }
                else{
                    other_sides+=arr[i];
                }
                if(other_sides>max)
                    return i+1;
            }
            return -1;
        }
    }
}
发表于 2019-08-15 01:35:27 回复(0)
n = int(input())
a = list(map(int,input().split()))
 
if n<3:
    print(-1)
elif n==3:
    a.sort()
    if a[0]+a[1]>a[2]:
        print(3)
    else:
        print(-1)
elif n>3:
    k=0
    for i in range(3,n):
        b = a[:i]
        b.sort()
        if sum(b[:-1])>b[-1]:
            print(i)
            k=1
            break
    if k==0:
        print(-1)

发表于 2019-08-14 10:51:48 回复(0)
Python版本的。
# 思路是n-1边的和大于最长边,就能组成封闭多边形;
N = int(input())
flag=1
temp = input().split(" ")
temp = list(map(int, temp))
if N < 3:
    print(-1)
else:
    for length in range(3,N+1):
        tamp=temp[0:length]
        tamp.sort()
        if sum(tamp[0:-1])>tamp[-1]:
            flag=0
            print(length)
            exit()
        else:
            flag=-1
    if flag == -1:
        print(-1)


发表于 2019-08-14 10:42:48 回复(0)
n=int(input())
ticks=list(map(int,input().strip().split()))
i=2
flag=0
while i<n:
    a=sorted(ticks[:i+1])
    if sum(a[:i])>a[-1]:
        flag=1
        break
    i+=1
if flag:
    print(i+1)
else:
    print(-1)
发表于 2019-08-13 00:15:32 回复(0)
#include<iostream>
#include<vector>
using namespace std;
int getMaxNumI(vector<int>s) {
	int max = 0;
	int k = -1;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] > max) {
			max = s[i];
			k = i;
		}
	}
	return k;
}
bool find(vector<int>s, int k) {
	int sum = 0;
	int i = 0;
	for (int i = 0; i < s.size(); i++) {
		if (i != k) sum += s[i];
	}
	if (sum > s[k]) return true;
	else return false;
}
int main() {
	int n;
	cin >> n;
	int res = -1;
	if (n < 3) {
		cout << res;
		return 0;
	}
	int* num = new int[n];
	vector<int>s;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	for (int i = 0; i < n; i++) {
		s.push_back(num[i]);
		if (i >= 2) {
			int max = getMaxNumI(s);
			if (find(s, max)) {
				res = i+1;
				break;
			}
		}
	}
	cout << res;
}

发表于 2019-08-12 20:48:19 回复(0)
n = input()
a = input()
list_a = a.split()
list_a = list(map(int,list_a))
for i in range(3,len(list_a)+1):
    if 2 * max(list_a[:i]) < sum(list_a[:i]):
        print(i)
        break
else:
    print(-1)

发表于 2019-08-06 13:37:21 回复(0)
import sys
lines = sys.stdin.readlines()
n = int(lines[0].strip())
if n<=2:
    print(-1)
numbers = [int(n) for n in lines[1].strip().split()]
cur = numbers[:3]
cur.sort()
res = 3
def judge(nums):
    if nums[0]+nums[1]<=nums[2]:
        return 0
    else:
        return 1
     
while not judge(cur):
    if res == len(numbers):
        print(-1)
        break
    cur.append(numbers[res])
    res += 1
    cur.sort()
    cur[0] = cur[0]+cur[1]
    cur.pop(1)
else:
    print(res)

发表于 2019-08-05 17:22:22 回复(0)
#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int a,b,sum,max,temp;
    scanf("%d %d",&a,&b);
    max=a>b?a:b;
    sum=a+b;
    int i;
    for(i = 0; i < n-2; i++){
        scanf("%d",&temp);
        max=temp>max?temp:max;
        sum=sum+temp-max;
        if(max<sum){
            printf("%d\n",i+3);
            break;
        }else{
            sum+=max;
        }
    }
    if(i==n-2){
        printf("-1\n");
    }
    return 0;
}
发表于 2019-08-04 21:38:25 回复(0)