URAL 1303. Minimal Coverage（最小覆盖 数学啊 ）

Input

Output

Samples

1
-1 0
-5 -3
2 5
0 0

No solution

1
-1 0
0 1
0 0

1
0 1

题意：

最小区间覆盖，求使用最少的木板，能覆盖区间0----M！

PS:

按照贪心的思想；

每次找到左端点在未被覆盖区间的左端点的左边，且右端点最远的木板，

然后把要求的覆盖区间改为这个右端点到M这个区间。

把此时木板的右端点作为未被覆盖区间的左端点！

依次类推下去。

代码如下：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
    int l, r;
} a[100017];
int vis[100017];
bool cmp(node a, node b)
{
    return a.l < b.l;
}
int main()
{
    int m;
    while(~scanf("%d",&m))
    {
        memset(vis, 0,sizeof(vis));
        int x, y;
        int k = 0;
        while(1)
        {
            scanf("%d%d",&x,&y);
            if(x==0 && y==0)
            {
                break;
            }
            a[k].l = x, a[k].r = y;
            k++;
        }
        sort(a,a+k,cmp);
        int cont = 0;
        int num = 0, p = 0;
        int flag = 0;
        int ans = 0;
        for(int i = 0; ; i++)
        {
            if(cont >= m)
            {
                break;
            }
            int t_end = 0, tt = 0;
            while(num < k && a[num].l <= cont)
            {
                if(a[num].r > t_end)
                {
                    t_end = a[num].r;
                    tt = num;
                }
                num++;
            }
            if(t_end == 0)
            {
                flag = 1;
                break;
            }
            cont = t_end;
            vis[tt] = 1;
            ans++;
        }
        if(flag)
        {
            printf("No solution\n");
            continue;
        }
        printf("%d\n",ans);
        for(int i = 0; i < k; i++)
        {
            if(vis[i])
            {
                printf("%d %d\n",a[i].l,a[i].r);
            }
        }
        printf("\n");
    }
    return 0;
}

URAL 1303. Minimal Coverage（最小覆盖 数学啊 ）

原文：http://blog.csdn.net/u012860063/article/details/44540963