13 URAL1303 Minimal Coverage

给cnt条线段，要求覆盖[0,m]，问能否覆盖，至少需要多少条线段。

用贪心的想法，假设当前位置在now，那么此时添加一条线段使得左端点<=now，右端点最远，这样是最划算的，

下次继续添加这样一条线段，使得右端点最远，左端点<=上一条选的线段的右端点。

扫完所有线段，now的位置可以到达m，则有解，否则无解。

#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
    int l,r;
}e[100010];
bool cmp(node a,node b)
{
    if(a.l!=b.l) return a.l<b.l;
    return a.r<b.r;
}
int T,m,cnt,p[100010];
int main()
{
    int a,b,i,now,ans,next,f,o,cas=0;
    while(~scanf("%d",&m))
    {
        cnt=0;
        while(scanf("%d%d",&a,&b)&&(a||b))
        {
            e[cnt].l=a;
            e[cnt++].r=b;
        }
        sort(e,e+cnt,cmp);e[cnt].r=e[cnt].l=100000;
        now=ans=next=0;f=o=0;
        for(i=0;i<cnt;i++)
        {
            if(e[i].l<=now&&e[next].r<=e[i].r) next=i,o=1;
            if(e[i+1].l>now&&o)
            {
                o=0;
                now=e[next].r;
                p[ans++]=next;
            }
            if(now>=m)
            {
                f=1;
                printf("%d\n",ans);
                for(i=0;i<ans;i++) printf("%d %d\n",e[p[i]].l,e[p[i]].r);
                break;
            }
        }
        if(!f) puts("No solution");
    }
    return 0;
}

13 URAL1303 Minimal Coverage

原文：http://blog.csdn.net/u011032846/article/details/45442117