Minimal coverage (贪心，最小覆盖)

题目大意：先确定一个M，然后输入多组线段的左端和右端的端点坐标，然后让你求出来在所给的线段中能够

把[0, M] 区域完全覆盖完的最少需要的线段数，并输出这些线段的左右端点坐标。

思路分析：

线段区间的起点是0，那么找出所有区间起点小于0中的最合适的区间。

因为需要尽量少的区间，所以选择右端点更大的区间，它包含所选线段更大。

如果在所有区间中找到了解，且右端点小于M，则把找到的区间的右端点定为新的线段区间的起点。

 #include <iostream>

 #include <stdio.h>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 struct node

 {

     int L, R;

 }a[], b[];

 bool cmp(node a, node b)

 {

     return a.R > b.R;

 }

 int main()

 {

     int M;

     while(scanf("%d", &M) != EOF)

     {

         int Index = ;

         while()

         {

             scanf("%d%d", &a[Index].L, &a[Index].R);

             if(a[Index].L ==  && a[Index].R == )

                 break;

             ++Index;

         }

         sort(a, a+Index, cmp);

         int border = ;        // 起始边界点为0

         int cnt = ;

         while(border < M)

         {

             int i = ;

             for(; i < Index; ++i)

             {

                 // a[i].R >= border提交将会Runtime error

                 if(a[i].L <= border && a[i].R > border)

                 {

                     b[cnt] = a[i];

                     cnt++;

                     border = a[i].R;    // 更新边界点

                     break;

                 }

             }

             if(i == Index)

                 break;

         }

         if(border < M)

             cout << "No solution" << endl;

         else

         {

             cout << cnt << endl;

             for(int i = ; i < cnt; ++i)

                 cout << b[i].L << " " << b[i].R << endl;

         }

     }

     return ;

 }

巴特西

Minimal coverage (贪心，最小覆盖)

最新文章

热门文章