首页 > ACM题库 > HDU-杭电 > hdu 2308 Playground[解题报告]C++
2014
01-05

hdu 2308 Playground[解题报告]C++

Playground

问题描述 :

George has K <= 20 steel wires shaped in the form of half-circles, with radii a1, a2, . . . , aK. They can be soldered (connected) at the ends, in any angle. Is it possible for George to make a closed shape out of these wires? He does not have to use all the wires.
The wires can be combined at any angle, but may not intersect. Beware of floating point errors.

输入:

Each data set consists of a number 0 < K <= 20 on a line by itself, followed by a line of K space-separated numbers ai. Each number is in the range 0 < ai < 107, and has at most 3 digits after the decimal point.
The input will be terminated by a zero on a line by itself.

输出:

Each data set consists of a number 0 < K <= 20 on a line by itself, followed by a line of K space-separated numbers ai. Each number is in the range 0 < ai < 107, and has at most 3 digits after the decimal point.
The input will be terminated by a zero on a line by itself.

样例输入:

1
4.000
2
1.000 1.000
3
1.455 2.958 4.424
7
1.230 2.577 3.411 2.968 5.301 4.398 6.777
0

样例输出:

NO
YES
NO
YES


题意:给定若干条边,问能否用其中的一些组成多边形。
先排序,看前i个的和是否大于第i+1个,若大于则可以

这个证明表示不会。。

#define maxn 30
double a[maxn];
int main()
{
    int  n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
        {
            break;
        }
        int i;
        memset(a,0,sizeof(a));
        for(i=1;i<=n;i++)
        {
            scanf("%lf",&a[i]);
        }
        sort(a+1,a+n+1);
        double sum=0.0;
        int flag=0;
        for(i=1;i<=n;i++)
        {

            if(sum>=a[i])
            {
                flag=1;
                printf("YES\n");
                break;
            }
            sum+=a[i];
        }
        if(flag==0)
        {
            printf("NO\n");
        }
    }
    return 0;
}