圈地运动-360公司笔试题

圈地运动

题目：

圈地运动，就是用很多木棍摆在地上组成一个面积大于0的多边形～ 小明喜欢圈地运动，于是他需要去小红店里面买一些木棍，期望圈出一块地来。小红想挑战一下小明，所以给小明设置了一些障碍。障碍分别是： 1. 如果小明要买第i块木棍的话，他就必须把前i-1块木棍都买下来。 2. 买了的木棍都必须用在圈地运动中。 那么请问小明最少买多少根木棍，才能使得木棍围成的图形是个面积大于0多边形呢？

• 时间限制：1s
• 空间限制：65536K

输入描述:

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

输出描述:

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

示例1

输入

3
6 8 10

输出

3

说明

用三根6，8，10的木棍可以组成一个直角三角形的图形，其是一个面积大于0的图形

我的作答 编译器：C++11(clang++3.9)

#include <stdio.h>
 
int compare(int ai[10000], int k)
{
     
    int i;
    int max = ai[0], sum = 0;
    for(i = 0; i < k; ++i)
    {
        sum += ai[i];
        if(ai[i] > max) max = ai[i];
    }
    sum -= max;	//木棍中最长的一根长度必须小于其余所有木棍长度之和才可以 
    if(sum > max) return k;
    else return -1;
}
 
int main()
{
    int i, n, ai[10000];
    scanf("%d", &n);
    for(i = 0; i < n; ++i)
    {
        scanf("%d", &ai[i]);
    }
    for(i = 3; i <= n; ++i)
    {
        if(compare(ai, i) == -1) continue;
        else
        {
            printf("%d", i);
            return 0;
        }
    }
    printf("-1");
    return 0;
}