P1047 校门外的树

时间:2022-12-17 20:01:14

题目

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

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

想法

刚开始,我想通过判断相邻区间的右端点和左端点,来确定是否相交。但是提交,总是有几个测试点通不过。
然后,通过看别人的思路,我看到了一个非常简单的思路。可能是我把问题想得太复杂了。

就我知道而言该题有三种做法:

  • 数组标记法(刚开始我怕超时)
  • 端点判断法
  • 线段树

代码

数组标记法

#include<iostream>
using namespace std;
int main(){
    int a[10010];
    int L,M;
    int i,j;
    int sum = 0;
    cin>>L>>M;
    for(int i=0;i<=L;i++){
        a[i] = 0;
    }
    while(M--){
        cin>>i>>j;
        for(int k = i;k<=j;k++){
            if(a[k] == 0)a[k] = 1;
            //若该树要被移走,就标记为1
        }
    }
    for(int i = 0;i<=L;i++){
        if(a[i] == 0)sum++;
    }
    cout<<sum<<endl;
    return 0;
}

端点判断法

#include<iostream>
#include<algorithm>
using namespace std;
int L,M;
int nStart,nEnd;
int sum = 0;
int q=1;
struct node{
    int l;
    int r;
}Section[101];
int mySort(node x, node y){
    return x.l < y.l;
}
int main(){
    cin>>L>>M;
    //赋值
    for(int i=1;i<=M;i++){
        cin>>nStart>>nEnd;
        Section[i].l = nStart;
        Section[i].r = nEnd;
    }
    //排序
    sort(Section+1,Section+M+1,mySort);
    //如果前面区间的右端点小于后面区间的左端点,则相交
    //如果前面区间的右端点大于后面区间的右端点,则重合
    //下面为构造新区间,将合并重合的组成一个新区间
    for(int i=2;i<=M;i++){
        if(Section[i].l > Section[q].r)Section[++q] = Section[i];
        else Section[q].r = max(Section[q].r , Section[i].r);
    }
    for(int i = 1;i<=q;i++){
        sum += Section[i].r - Section[i].l+1;
    }
    cout<<L-sum+1<<endl;
    return 0;
}

个人博客:陪你一起终身学习!|岳金钊&个人博客