首页 > 试题广场 >

圈地运动

[编程题]圈地运动
  • 热度指数:3052 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

圈地运动,就是用很多木棍摆在地上组成一个面积大于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边的和大于最长边,就能组成封闭多边形
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)
# 思路是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)
#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)
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 <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 = int(input())
ls = list(map(int,input().split()))
count = 3
pick = ls[0:3]
maximum = max(pick)
t_m = sum(pick) - maximum
while t_m<=maximum and count<=n-1:
    if ls[count]>maximum:
        t_m += maximum
        maximum = ls[count]
        
    else:
        t_m += ls[count]
    count +=1
if t_m > maximum:
    print(count)
else:
    print(-1)

发表于 2021-03-28 18:45:05 回复(0)
通过率70%, 哪位大佬可以看一下哪里出错了啊。找不到原因

import java.lang.System;
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] gun = new int[n];
        for(int i =0; i<n; i++){
            gun[i]=sc.nextInt();
        }
    
        if(n<3){
            System.out.println(-1);
        }
        int sum=0;
        int max=0;
    
        int result=-1;
        
        for(int j = 0; j<n; j++){
            sum +=gun[j];
            max = Math.max(max, gun[j]);
            if(j>2 && sum>(2*max)){
                //System.out.println(j+1);
                result =j+1;
                break;
            }
        }
        System.out.println(result);
}}
发表于 2020-08-22 02:40:57 回复(0)
// n-1边的和大于最长边可以构成封闭多边形
#include<bits/stdc++.h>
using namespace std;

class Solution{
    public:
       int getMinNum(vector<int> arr){
           if(arr.size() < 3){
               return -1;
           }
           int maxLen = INT_MIN;
           int sum = 0;
           for(int i=0;i<arr.size();i++){
              sum +=arr[i];
              maxLen = max(maxLen,arr[i]);
              if(i > 1){
                  if(sum - maxLen > maxLen){
                      return i+1;
                  }
              }
              
           }
           return -1;
       }
};

int main(){
    int  n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    Solution c1;
    cout<<c1.getMinNum(arr)<<endl;
    return 0;
}

发表于 2020-06-02 23:31:53 回复(0)
import java.util.Scanner;

/**
 * @author :xbb
 * @date :Created in 2020/3/27 8:58 上午
 * @description:牛客网刷题
 * @modifiedBy:
 * @version:
 */
public class Main {

    public static void main(String[] args) {
        Enclosure();
    }

    /**
     * 圈地运动链接:
     * 圈地运动,就是用很多木棍摆在地上组成一个面积大于0的多边形~
     * 小明喜欢圈地运动,于是他需要去小红店里面买一些木棍,期望圈出一块地来。
     * 小红想挑战一下小明,所以给小明设置了一些障碍。障碍分别是:
     * 1.如果小明要买第i块木棍的话,他就必须把前i-1块木棍都买下来。
     * 2.买了的木棍都必须用在圈地运动中。
     * 那么请问小明最少买多少根木棍,才能使得木棍围成的图形是个面积大于0多边形呢?
     * 输入描述:
     * 第一行一个数n,表示木棍个数。
     * 第二行n个数,第i个数表示第i个木棍的长度ai
     * 1<=n<=10000
     * 1<=ai<=10000
     * 输出描述:
     * 输出一个数,表示最少需要的木棍个数,如果无解输出-1
     * 示例1
     * 输入
     * 3
     * 6 8 10
     */
    private static void Enclosure() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        if (n < 3) {
            System.out.println(-1);
        }
        Double max = 0D;
        Double sum = 0D;

        for (int i = 0; i < n; i++) {
            Double x = in.nextDouble();
            max = max > x ? max : x;
            sum += x;
            if (sum-max > max) {
                System.out.println(i+1);
                break;
            }
        }
        if (sum-max <= max){
            System.out.println(-1);
        }
    }
}


发表于 2020-03-27 12:38:56 回复(0)

#include <iostream>
#
include <algorithm>
 
using namespace std;
 
int getsum(int a[],int num){
    int sum=0;
    for(int i=0;i<num;i++){
        sum+=a[i];
    }
    return sum;
}
 
int main(){
    int n;
    int i;
    cin>>n;
    int a[10000];
    cin>>a[0]>>a[1];
    for(i=2;i<n;i++){
        cin>>a[i];
        sort(a,a+i+1);
        int sum=getsum(a,i);
        if(sum>a[i]){
            cout<<i+1<<endl;
            break;
        }
    }
    if(i>=n){
        cout<<-1<<endl;
    }
 
}

同用思想:最小边之和大于最大边,可以围城多边形。
error:int a[10000];   sizeof(a)结果是10000,而不是具体给a赋值的个数。
发表于 2020-03-24 12:05:48 回复(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)