提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

UVA10020(最小区间覆盖)

最小 覆盖 区间
2023-09-11 14:14:00 时间
题意：
      给你一个区间[0,m]和一些小的区间[l,r]让你选择最少的小区间个数去把整个区间覆盖起来。


思路：
      算是比较经典的贪心题目吧（经典于难度没什么对应关系），大体思路可以是这样，我们先把所有的区间按照起点从小到大排序，然后我们定义一个当前覆盖位置pos,初始是0，也就是[0,m]的最左端，然后我们从小区间中找到一个可以覆盖pos点并且右端点最远的一个（记得sum++）,然后把最远的这个右端点作为当前的pos，继续找下一个，至于实现，我是自己写的，可能写的不是很简洁，不知道网上有没有简洁点的，如果没有就讲究看下我的吧，具体细节看代码。



#include<stdio.h>
#include<algorithm>

#define N 110000


using namespace std;


typedef struct
{
   int l ,r;
}EDGE;

EDGE edge[N] ,Ans_edge[N];

bool camp(EDGE a, EDGE b)
{
   return a.l < b.l;
}

int main ()
{
   int m ,nowid ,i ,t ,a ,b;
   scanf("%d" ,&t);
   while(t--)
   {
      scanf("%d" ,&m);
      nowid = 0;
      while(1)
      {
         scanf("%d %d" ,&a ,&b);
         if(!a && !b) break;
         if(a > m || b < 0) continue;
         ++nowid;
         edge[nowid].l = a ,edge[nowid].r = b;
      }
      sort(edge + 1 ,edge + nowid + 1 ,camp);
      int Ans = 0 ,pos = 0 ,max = 0 ,mkid = 0;
      for(i = 1 ;i <= nowid ;i ++)
      {
         if(pos > edge[i].r) continue;
         if(edge[i].l <= pos)
         {
            if(max < edge[i].r) {max = edge[i].r ,mkid = i;}
            if(i == nowid)
            {
               if(max < m){Ans = 0 ;break;}
               Ans_edge[++Ans] = edge[mkid];
            }   
         }
         else
         {
            if(!max){Ans = 0; break;}
            pos = max;
            max = 0 ,Ans ++ ,i --;
            Ans_edge[Ans] = edge[mkid];
            if(pos >= m) break;
         }
      }
      printf("%d\n" ,Ans);
      for(i = 1 ;i <= Ans ;i ++)
      printf("%d %d\n" ,Ans_edge[i].l ,Ans_edge[i].r);
      if(t) printf("\n");
   }
   return 0;
}
   
      
            
            
      
      
   
   
    





相关文章