codevs1214 线段覆盖(贪心)-白红宇

codevs1214 线段覆盖(贪心)

阅读量：4542 次

发布时间：2019-06-08

本文共 1610 字，大约阅读时间需要 5 分钟。

题目描述

Description

给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些坐标都是区间（－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。

输入描述

Input Description

输入第一行是一个整数N。接下来有N行，每行有二个空格隔开的整数，表示一条线段的二个端点的坐标。

输出描述

Output Description

输出第一行是一个整数表示最多剩下的线段数。

样例输入

Sample Input

6 3

1 3

2 5

样例输出

Sample Output

数据范围及提示

Data Size & Hint

0<N<100

先对所有线段按起点优先终点次之排好序。

在两线段冲突的情况下，应尽可能保留终点小的（因为终点大的更可能与后面的冲突）。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;#define debug(x) cout<<"debug "<
                   
                    <
                    
                     = _end_; --i)#define dep2(i,f,t) for(int i = (f),_end_=(t); i > _end_; --i)#define clr(c, x) memset(c, x, sizeof(c) )typedef long long int64;const int INF = 0x5f5f5f5f;const double eps = 1e-8;//*****************************************************bool del[110];pair
                     
                       p[110];#define a first#define b secondinline int len(int i){ return p[i].b - p[i].a;}int main(){ int n; scanf("%d",&n); for(int i = 1; i <= n; ++i) { scanf("%d%d",&p[i].a,&p[i].b); if(p[i].a > p[i].b)swap(p[i].a, p[i].b); } sort(p+1,p+n+1); for(int i = 1; i < n; ++i)if(!del[i]){ for(int j = i+1; j <= n; ++j){ if(p[j].a >= p[i].b)break; if(p[i].b >= p[j].b){ del[i] = 1; break; }else{ del[j] = 1; continue; } } } int ans = n; for(int i = 1; i <= n; ++i)if(del[i])--ans; printf("%d\n",ans); return 0;}

转载于:https://www.cnblogs.com/DSChan/p/4862028.html

你可能感兴趣的文章