计蒜客蓝桥杯模拟二区间合并打扫教室-白红宇

计蒜客蓝桥杯模拟二区间合并打扫教室

阅读量：6289 次

发布时间：2019-06-22

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

一天蒜头君被要求打扫

现在告诉你蒜头君打扫了哪些教室，你能告诉蒜头君他还有多少间教室没有打扫吗？

输入格式

第一行输入两个整数

接下来

输出格式

输出一个整数，表示蒜头君还有多少间教室没有打扫。

数据范围

对于 $50\%50% 的数据：1 \le n, m \le 10^31≤n,m≤103。$

对于 $100\%100% 的数据：1 \le n,m \le 10^6, 1 \le l \le r \le n1≤n,m≤106,1≤l≤r≤n。$

样例输入复制

10 31 53 79 10

样例输出复制

1 题解： 先将区间进行排序，排序后的区间只有相交和不相交两种。当前右边端点大于后面的左边端点时则两个区间相交，否则不相交 然后用总数减去每个相交区间所含个数得到结果

#include #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #define ls (r<<1)#define rs (r<<1|1)#define debug(a) cout << #a << " " << a << endlusing namespace std;typedef long long ll;const ll maxn = 1e6+10;const ll mod = 10086;const double pi = acos(-1.0);const double eps = 1e-8;struct node { ll le, ri;};node a[maxn];bool cmp( node p, node q ) { if( p.le == q.le ) { return p.ri < q.ri; } return p.le < q.le;}int main() { ll n, m; scanf("%lld%lld",&n,&m); for( ll i = 0; i < m; i ++ ) { scanf("%lld%lld",&a[i].le,&a[i].ri); } sort(a,a+m,cmp); ll le = a[0].le, ri = a[0].ri; for( ll i = 1; i < m; i ++ ) { if( ri >= a[i].le ) { le = min(le,a[i].le); ri = max(ri,a[i].ri); } else { n = n - (ri-le+1); le = a[i].le; ri = a[i].ri; } } n = n - (ri-le+1); printf("%lld\n",n); return 0;}