ural Minimal Coverage (区间覆盖) - c++编程基础

TOP

ural Minimal Coverage (区间覆盖)

2015-07-20 17:49:03 来源: 作者: 【大中小】浏览:1次

给出一些区间，选择尽量少的区间能覆盖到[0,m]。

小白p154，典型的区间覆盖问题。一直在想怎么dp。。

首先预处理，先按左端点从小到大排序，若左端点相同右端点从大到小排序，若区间x完全包含y，按照贪心的思想，y是没有意义的，有大区间可以选何必选择小区间。处理完事之后各个区间满足a1 <= a2 <= a3....且b1 <= b2 <= b3...

这样找到第一个覆盖0的区间之后，记录上一个区间所能到达的最右边位置，然后去找一个左端点最接近该位置的区间继续覆盖，直到覆盖到M点。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #define LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 4010; struct Line { int l,r; bool operator < (const struct Line &tmp)const { if(l == tmp.l) return r > tmp.r; return l < tmp.l; } } b[100010],a[100010],ans[100010]; int main() { int m,t1,t2; while(~scanf(%d,&m)) { int l,r; t1 = 0; while(~scanf(%d %d,&l,&r)) { if(l == 0 && r == 0) break; a[++t1] = (struct Line){l,r}; } sort(a+1,a+1+t1); t2 = 1; b[1] = a[1]; for(int i = 2; i <= t1; i++) { if(a[i].r < 0 || a[i].l > m) continue; if(!(a[i].l >= b[t2].l && a[i].r <= b[t2].r))//包含的区间去掉 b[++t2] = a[i]; } t2++; b[t2] = (struct Line){m+1,m+1}; int k = 0; int e = -1,i; for(i = 1; i < t2; i++) { if(b[i].l <= 0 && b[i+1].l > 0) { ans[++k] = b[i]; e = b[i].r; break; } } if(k == 0) { printf(No solution ); continue; } for(; i < t2; i++) { if(e >= m) break; if(b[i].l <= e && b[i+1].l > e) //找到最接近上一个区间端点的区间覆盖 { ans[++k] = b[i]; e = b[i].r; } } if(e < m) { printf(No solution ); continue; } else { printf(%d ,k); for(int i = 1; i <= k; i++) { printf(%d %d ,ans[i].l,ans[i].r); } } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：11922 - Permutation Transformer..	下一篇：zoj 3666 Alice and Bob ， SG函数

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: