首页 > 代码库 > Tyvj - 1286 - 校门外的树2

Tyvj - 1286 - 校门外的树2

2024-07-12 18:41:12   214人阅读

描述 Description
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
 
 
 
 
输入格式 InputFormat
输入的第一行有两个整数L（1 <= L <= 1亿）和 M（1 <= M <= 20000），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

 
 
 
 
输出格式 OutputFormat
输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
 
样例输入 SampleInput

500 3
150 300
100 200
470 471

 

样例输出 SampleOutput

298

 

　　昨天的排位赛又掉进大坑里面了，然后将题解的时候马哥说有兴趣的话可以去看一下校门口的树1 2 3。然后目前看了1和2，题意基本相同，但是1的数据量很小，直接模拟即可，2的数据量有点大，范围最大可以到一亿，这里一开始想试一下离散化+树状数组，结果发现离散化以后不知道怎样用树状数组了，然后又想起自己之前一直不敢做这种题，于是就试了一下快排+扫描，结果还真过了→_→，基础知识捉急啊（┬＿┬） 。

　　记录一下想法吧，逼近之前一直觉得这是什么大难题，其实只是当时没有动脑子（┬＿┬） 。

　　先对区间排个序，要求如果左端点小的就排在前面，如果左端点相等的话就根据右端点大的排前面。

　　然后从左向右扫描，用一个变量rr记录当前访问的所有线段里面我们遇到过的最大的右端点是多少，然后每一次访问新的线段的时候就新线段的左端点和r比较一下，如果比rr大就说明新线段前面有一段(rr,新线段)没有被覆盖。

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <vector> 5 #include <algorithm> 6 #define MAX 20002 7 using namespace std; 8  9 typedef struct Seg{10     int l,r;11 12     bool operator < (const Seg& o)const{13         return l==o.l ? r>o.r: l<o.l ;14     }15 }Seg;16 17 Seg v[MAX];18 int L,m;19 20 int main()21 {22     ios::sync_with_stdio(false);23     //freopen("data.txt","r",stdin);24     int sum;25     while(cin>>L>>m){26         for(int i=0;i<m;i++){27             cin>>v[i].l>>v[i].r;28             if(v[i].l>v[i].r) swap(v[i].l,v[i].r);29         }30         sort(v,v+m);31         sum=v[0].l-0;32         int rr=v[0].r;33         for(int i=1;i<m;i++){34             if(v[i].l>rr) sum+=v[i].l-rr-1;35             rr = max(rr,v[i].r);36         }37         sum+=L-rr;38         cout<<sum<<endl;39     }40     return 0;41 }42 #include <cstdio>43 #include <cstring>44 #include <iostream>45 #include <vector>46 #include <algorithm>47 #define MAX 2000248 using namespace std;49 50 typedef struct Seg{51     int l,r;52 53     bool operator < (const Seg& o)const{54         return l==o.l ? r>o.r: l<o.l ;55     }56 }Seg;57 58 Seg v[MAX];59 int L,m;60 61 int main()62 {63     ios::sync_with_stdio(false);64     //freopen("data.txt","r",stdin);65     int sum;66     while(cin>>L>>m){67         for(int i=0;i<m;i++){68             cin>>v[i].l>>v[i].r;69             if(v[i].l>v[i].r) swap(v[i].l,v[i].r);70         }71         sort(v,v+m);72         sum=v[0].l-0;73         int rr=v[0].r;74         for(int i=1;i<m;i++){75             if(v[i].l>rr) sum+=v[i].l-rr-1;76             rr = max(rr,v[i].r);77         }78         sum+=L-rr;79         cout<<sum<<endl;80     }81     return 0;82 }
1286

 


联系
我们