P1047 校门外的树

admin

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

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入输出格式
输入格式：
输入文件tree.in的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出格式：
输出文件tree.out包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

输入输出样例
输入样例#1：
500 3
150 300
100 200
470 471
输出样例#1：
298
说明
NOIP2005普及组第二题

对于20%的数据，区域之间没有重合的部分；

对于其它的数据，区域之间有重合的情况。

GTR

程序：
#include <iostream>
using namespace std;
int l,m;
int main ()
{
cin>>l>>m;
int *p=new int [l+1];
for(int i=0;i<l+1;i++)
*(p+i)=1;
for(int i=0;i<m;i++)
{
int t1,t2;
cin>>t1>>t2;
for(int j=t1;j<=t2;j++)
*(p+j)=0;
}
int count=0;
for(int i=0;i<l+1;i++)
if(*(p+i)) count++;
cout<<count<<endl;
return 0;
}

universehyf

#include<iostream>
using namespace std;
int a[10001]={};
int main()
{
        int m,n,d,b,c=0;
        cin>>m>>n;
        for(int i=1;i<=n;i++)
        {
                cin>>d>>b;
                for(int j=d;j<=b;j++) a[j]=1;
        }
        for(int i=0;i<=m;i++)
                if(!a[i]) ++c;
        cout<<c;
        return 0;
}

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. int l,m,i,j,s=0;
   
4. int main()
   
5. {
   
6.     cin>>l>>m;
   
7.     int a,b,t[l];
   
8.     for(i=0;i<=l;i++)
   
9.         t[i]=1;
   
10.     for(i=0;i<=m-1;i++)
    
11.      {
    
12.        cin>>a>>b;
    
13.        for(j=a;j<=b;j++)
    
14.         t[j]=0;
    
15.      }  
    
16.     for(i=0;i<=l;i++)
    
17.         if(t[i]==1)s++;
    
18.     cout<<s;
    
19.     return 0;
    
20. 
    
21. }
    

复制代码

WJL

1. #include <iostream>
   
2. using namespace std;
   
3. int main ()
   
4. {
   
5. int l,m;
   
6. cin>>l>>m;
   
7. int *p=new int [l+1];
   
8. for(int i=0;i<l+1;i++)
   
9. *(p+i)=1;
   
10. for(int i=0;i<m;i++)
    
11. {
    
12. int temp1,temp2;
    
13. cin>>temp1>>temp2;
    
14. for(int j=temp1;j<=temp2;j++)
    
15. *(p+j)=0;
    
16. }
    
17. int count=0;
    
18. for(int i=0;i<l+1;i++)
    
19. if(*(p+i)) count++;
    
20. cout<<count<<endl;
    
21. return 0;
    
22. }

复制代码

张笑宇

1. <div class="blockcode"><blockquote>#include<iostream>
   
2. using namespace std;
   
3. const int mx=10010;
   
4. int a[mx],b[mx],c[mx];
   
5. int i,j;
   
6. int l,n;
   
7. int main()
   
8. {
   
9.     cin>>l>>n;
   
10.     for (i=1;i<=n;i++) cin>>a[i]>>b[i];
    
11.     for (i=0;i<=mx-1;i++) c[i]=true;
    
12.     for (i=1;i<=n;i++)
    
13.     {
    
14.         for (j=a[i];j<=b[i];j++) c[j]=false;
    
15.     }
    
16.     int sum=0;
    
17.     for (i=0;i<=l;i++) if (c[i]==true) sum++;
    
18.     cout<<sum;
    
19.     return 0;
    
20. }
    

复制代码

xpb

1. #include<iostream>
   
2. using namespace std;
   
3. const int mn=10001;
   
4. int l,m,s[mn],e[mn],k[mn],i,j,numb;
   
5. int main()
   
6. {
   
7.     cin>>l>>m;
   
8.     for(i=1; i<=m; i++)
   
9.     {
   
10.         cin>>s[i]>>e[i];
    
11.     }
    
12.     for(i=0; i<=l; i++)
    
13.     {
    
14.         k[i]=1;
    
15.     }
    
16.     for(i=1; i<=m; i++)
    
17.     {
    
18.         for(j=s[i]; j<=e[i]; j++)
    
19.         {
    
20.             k[j]=0;
    
21.         }
    
22.     }
    
23.     for(i=0; i<=l; i++)
    
24.     {
    
25.         if(k[i]==1)
    
26.         {
    
27.             numb++;
    
28.         }
    
29.     }
    
30.     cout<<numb;
    
31.     return 0;
    
32. }
    

复制代码