圈地运动

柔情只为你懂 2022-05-11 04:20 171阅读 0赞

**题目：**

> 给n个木棒以及木棒的长度，求最少能构成多边形的木棒数目。要求如果选择第i个木棒，就必须选择前面的(i-1)个，即要按照木棒给出的顺序来选择。如果不能构成多边形，则返回-1；否则返回构成多边形的木棒数量。

**示例1：**

> **输入描述：**
> 
>     3
>     
>     6 8 10 
> 
> **输出描述**
> 
>     3

**示例2：**

> **输入描述：**
> 
>     5
>     
>     1 2 3 6 10
> 
> **输出描述：**
> 
>     5

**原理：**

> **前n根之和大于第n根才能组成一个多边形，若想等即为一条直线。**

**代码实现：**

> **C++版本 **
> 
>     #include<iostream>
>     #include<algorithm>
>     #include<vector>
>     using namespace std;
>     
>     int count(vector<int> arr)
>     {
>     	int result = 0;	//返回结果
>     
>     	sort(arr.begin(), arr.end());//对输入的长度进行排序
>     	int sum = arr[0] + arr[1];  //作为判断的依据
>     	for (unsigned int i = 2; i < arr.size(); i++)
>     	{
>     		
>     		if (sum > arr[i])//两边之和大于第三边
>     		{
>     			result = i + 1;
>     			return result;
>     		}
>     		else
>     		{
>     			sum += arr[i];
>     		}	
>     	}
>     	return 0;
>     }
>     int main()
>     {
>     	int N;
>     	int result = 0;
>     	vector<int> arr;
>     	while(cin >> N)//连续输入
>     	{
>     		while (N--)
>     		{	
>     			int temp;
>     			cin >> temp;
>     			arr.push_back(temp);
>     		}	
>     	result = count(arr);
>     	cout << result;
>     	}
>     	system("pause");
>     	return 0;
>     }
> 
> **Python版本**
> 
>     #coding=utf-8
>     #输入n
>     n = int(input())
>     #输入n条边长度
>     gun_length = list(map(int, input().split()))
>     
>     #三角形判断准则，两边之差小于第三边，两边之和大于第三边
>     def select(a, b, c):
>         if a - b < c and a + b > c:
>             return 1
>         else:
>             return 0
>     
>     #判断过程
>     if n > 3:
>         for i in range(n - 2):
>             num_list = []
>             num_list = list(gun_length[:3 + i])
>             #假如前三条边满足三角形准则，那么返回3。否则，比较除最长边之外的和与最长边长度比较。
>             if i == 0:
>                 a, b, c = (i for i in num_list)
>                 r = select(a, b, c)
>                 if r == 1:
>                     print(3)
>             else:
>                 if (3+i) < n:
>                     max_num = max(num_list)
>                     max_num_index = num_list.index(max_num)
>                     del(num_list[max_num_index])
>                     if sum(num_list) > max_num :
>                         print(len(num_list) + 1)
>                     else:
>                         continue
>                 else:
>                     max_num = max(num_list)
>                     max_num_index = num_list.index(max_num)
>                     del(num_list[max_num_index])
>                     if sum(num_list) > max_num :
>                         print(len(num_list) + 1)
>                     else:
>                         print(-1)
>     
>     elif n == 3:
>         a, b, c = (i for i in gun_length)
>         r = select(a, b, c)
>         if r == 1:
>             print(n)
>         else:
>             print(-1)
>     else:
>         print(-1)
> 
>