首页 > 代码库 > zoj 2811 - Playground

zoj 2811 - Playground

题目:有很多个半圆环,问能不能拼成闭合图形,这里可以任意角度端点拼接。

分析:贪心。开始以为是搜索3^20觉得有点大,一看可以任意角度链接。

            把range按递增序排序,每次检测前面的所有range的和是否大于当前的range;

            如果前面的和大,则可以构成闭合图形;否则将它加入前面的集合,向下判断;

            那么这种情况一定能取到所有的解么?

            如果存在闭合图形,他的取的所有半圆构成一个集合,那么其中一定有个最大值;

            而剩下的半圆的子集一定可以组成一个不小于他的图形,那么全集一定也可以;

            二如果全集(不包含最大值)不能组成一个不小于最大值的图形,那子集一定不行;

            所以取去掉最大值剩下的元素的全集判断,即为上面叙述的方法。

说明:大黄用的区间松弛,不过可以证明,和贪心等价。(2011-09-27 00:22)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

double hc[ 21 ];

int cmp( const void* a, const void* b )
{
    double *p = (double *)a;
    double *q = (double *)b;
    if ( *p < *q ) return -1;
    else return 1;
}

int main()
{
    int K;
    while ( scanf("%d",&K) != EOF ) {
        if ( !K ) break;
        for ( int i = 0 ; i < K ; ++ i )
            scanf("%lf",&hc[ i ]);
        
        qsort( hc, K, sizeof( double ), cmp );
        
        int flag = false;
        double sum = hc[ 0 ];
        for ( int i = 1 ; i < K ; ++ i ) {
            if ( hc[ i ]-sum < 1e-4 ) {
                flag = true;
                break;
            }
            sum += hc[ i ];
        }
        
        if ( flag ) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

zoj 2811 - Playground