首页 > 试题广场 >

校门外的树

[编程题]校门外的树

热度指数：12179 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

输入描述:

第一行输入两个整数 ，用空格隔开，表示马路的长度和地铁施工区域数，满足 ，。

接下来  行，每行输入两个整数 ，用空格隔开，表示第  个施工区域的起始点和终止点的坐标，满足 。

输出描述:

输出一个整数，表示移除所有施工区域内（包括端点）树后，剩余的树的总棵树数。

示例1

输入

输出

说明

马路上共有  棵树。施工区域 [150,300] 中含有  棵，[100,200] 中含有  棵，[470,471] 中含有  棵。三个区域的重叠部分 [150,200] 有  棵被重复移除，所以实际移除的树数为 ，因此剩余  棵。

示例2

输入

10 2
2 5
4 8

输出

说明

马路上共有  棵树。区域 [2,5] 移除  棵，区域 [4,8] 移除  棵。重叠部分 [4,5] 有  棵被重复移除，所以实际移除  棵，剩余  棵。

备注:

算法知识视频讲解

牛客163642381号

用set

l, m = map(int, input().split())

s = set()

for i in range(m):

a, b = map(int, input().split())

s.update(range(a, b+1))

print(l + 1 - len(s))

发表于 2025-06-18 11:36:36 回复(0)

Python3

禊月初三

L, M = map(int, input().split())

trees = [1] * (L + 1)

for i in range(M):
    a, b = map(int, input().split())
    for j in range(a, b + 1):
        trees[j] = 0

print(sum(trees))

发表于 2025-07-07 15:38:40 回复(2)

Python3

意若久时天然呆

L, M = map(int, input().split())
t = [1] * (L + 1)
for _ in range(M):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        t[j] = 0
print(sum(t))

发表于 2025-11-04 16:18:18 回复(0)

GB279824

l,m = map(int,input().strip().split())

regin = []
for _ in range(m):
    a,b = map(int,input().strip().split())
    regin.append((a,b))

totals = l +1
remove_trees = overlaps = 0

removed = [False] * (l+1)

for (a,b) in regin:
    for i in range(a,b+1):
        if not removed[i]:
            remove_trees += 1
            removed[i] = True
        else:
            overlaps += 1

remain = totals - remove_trees
print(remain)

发表于 2025-06-07 21:42:21 回复(1)

Python3

鼣人

L, M = map(int, input().split())

# 初始化所有树都在

trees = [1] * (L + 1) # 1表示有树，0表示被移走

for i in range(M):

start, end = map(int, input().split())

# 把这段区间的树都移走（标记为0）

for j in range(start, end + 1):

trees[j] = 0

shengyu_trees = sum(trees)

print(shengyu_trees)

正常施工路段应该不会重合吧

发表于 2025-09-26 11:22:07 回复(0)

Python3

想回学校的牛油少糖去冰

n,M=map(int,input().split())

L=[1]*(n+1)

for _ in range(M):

l,r=map(int,input().split())

for i in range(l,r+1):

L[i]=0

print(sum(L))

发表于 2025-06-24 16:16:05 回复(0)

Python 3

牛牛大王不怕苦难

l, m = map(int, input().split(" "))
node_lst = []
flag = 0
cnt = 0
for i in range(0, m):
    x, y = map(int, input().split(" "))
    node_lst.append([x, 1])
    node_lst.append([y, -1])
    node_lst.sort()

start_node = node_lst[0][0]
for j in range(0, len(node_lst)):
    flag = flag + node_lst[j][1]
    if flag == 0:
        end_node = node_lst[j][0]
        yc_cnt = end_node - start_node + 1
        cnt += yc_cnt
        if j + 1 < len(node_lst):
            start_node = node_lst[j + 1][0]
print(l - cnt + 1)

发表于 2025-12-19 16:09:23 回复(0)

C++

来吾告汝

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

class ComparePair {
  public:
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
        return a.first < b.first;
    }
};

int main() {
    int L, M;
    cin >> L >> M;
    vector<pair<int, int>> intervals;
    intervals.reserve(M); 

    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        intervals.emplace_back(x, y);
    }

    sort(intervals.begin(), intervals.end(), ComparePair());

    vector<pair<int, int>> merged_intervals;
    if (!intervals.empty()) {
        auto it = intervals.begin();
        int cur_start = it->first;
        int cur_end = it->second;

        for (++it; it != intervals.end(); ++it) {
            if (it->first <= cur_end + 1) {
                cur_end = max(cur_end, it->second);
            } else {
                merged_intervals.emplace_back(cur_start, cur_end);
                cur_start = it->first;
                cur_end = it->second;
            }
        }
        merged_intervals.emplace_back(cur_start, cur_end);
    }

    int covered_count = 0;
    for (const auto& seg :
            merged_intervals) { 
        covered_count += seg.second - seg.first + 1;
    }

    cout << (L + 1 - covered_count) << endl;

    return 0;
}

发表于 2025-12-16 00:56:17 回复(0)

大便王

#include<bits/stdc++.h>

using namespace std;

int main()

{

unordered_set<int>x;

int l,m;

cin>>l>>m;

while(m--)

{

int a,b;

cin>>a>>b;

for(int i=a;i<=b;i++) x.insert(i);

}

cout<<l-x.size()+1;

return 0;

}

发表于 2025-12-09 23:14:35 回复(0)

unji_trip523

这是我的答案，虽然跟使一样但是我觉得很好理解也很直接
#include <stdio.h>

int main() {
    int L,M;
    scanf("%d %d",&L,&M);
    int tree[20000]={0};
    for(int i=0;i<=L;i++){
        tree[i]=1;
    }
    int l[M];
    int r[M];
    for(int i=0;i<M;i++){
        scanf("%d %d",&l[i],&r[i]);
    }
    for(int i=0;i<M;i++){
        for(int j=l[i];j<=r[i];j++){
            tree[j]=-1;
        }
    }
    int cnt=0;
    for(int i=0;i<=L;i++){
        if(tree[i]==1){
            cnt++;
        }
        // printf("%d.%d ",i,tree[i]);
    }
    printf("%d",cnt);

    
    return 0;
}

发表于 2025-12-07 21:17:13 回复(0)

牛客915416951号

#include <stdio.h>

int main(){

int l,m,min,max,arr[10001];

int count = 0;

scanf("%d %d\n",&l,&m);

for(int i = 0;i<=l;i++)arr[i]=1;

for(int i=0;i<m;i++){

scanf("%d %d\n",&min,&max);

for(int j = min; j <= max; j++){

arr[j] = 0;

}

for(int i = 0; i<=l;i++){

if(arr[i] == 1)count ++;

}

printf("%d\n",count);

}

发表于 2025-11-15 16:51:54 回复(0)

牛客908710302号

保存和提交会有这样的错误，哪里来的10组用例？

发表于 2025-11-12 14:16:31 回复(0)

pypy3

农骆驼

l, m = map(int, input().split())
t = [1] * (l+1)
for _ in range(m):
    a, b = map(int, input().split())
    for i in range(a,b+1):
        t[i] = 0
x = sum(t)
print(x)

发表于 2025-11-11 22:06:32 回复(0)

甲醇苯酚钠

#include <iostream>
using namespace std;
#include<vector>
int main() {
   int L,M;
   cin>>L>>M;
   vector<int>v;
   v.resize(L+1);
   for(int i=0;i<v.size();i++){
    v[i]=0;
   }
   while(M--){
     int l,r;
     cin>>l>>r;
     for(int i=l;i<=r;i++){
        if(v[i]==0){
            v[i]=1;
        }
     }
   }
   int sum=0;
   for(int i=0;i<v.size();i++){
    if(v[i]==0){
        sum++;
    }
   }
   cout<<sum;
}

发表于 2025-11-05 16:30:54 回复(0)

牛客942052331号

import sys

datas = [line.strip().split() for line in sys.stdin]

L,M = map(int,datas[0])
arr = set()
for data in datas[1:]:
    l,r = map(int,data)
    arr.update(list(range(l,r+1)))
print(L+1-len(arr))

发表于 2025-10-29 10:20:01 回复(0)

精益求精b

import sys

L,M = map(int,input().split())

list = [i*0 for i in range(0,L+1)]

for i in range(1,M+1):

li,ri = map(int,input().split())

list[li:ri+1] = [1] * (ri - li + 1)

cnt = list.count(0)

print(cnt)

发表于 2025-10-24 12:01:07 回复(0)

吴坤桓

L, M = map(int, input().split())
state = [1 for i in range (L + 1)]
for i in range (M): 
    a, b = map(int, input().split())
    state[a:b+1] = [0] * (b - a + 1)
print(sum(state))

列表由1替换为0，直接用sum，容易理解

发表于 2025-10-14 14:56:49 回复(0)

C++

凉皮真好吃

#include<bits/stdc++.h>

using namespace std;

int main(){

int L,M,sum;

int a[10010]={0};

cin>>L>>M;

for(int i=1;i<=M;i++)

{

int l,r;

cin>>l>>r;

for (int j=l;j<=r;j++)

{

a[j]=1;

}

for(int i=0;i<=L;i++)

{

if(a[i]==0)

sum=sum+1;

}

cout<<sum;

}

发表于 2025-10-11 18:55:15 回复(0)

kutwafter

#include <stdio.h>

int main() {

int a, b;

int c[100];

int d[100];

scanf("%d %d",&a,&b);

for(int i=0;i<b;i++)

{

scanf("%d %d",&c[i],&d[i]);

}

int sc[a+1];

for(int i=0;i<=a;i++)

{

sc[i]=1;

}

for(int i=0;i<b;i++)

{

for(int j=c[i];j<=d[i];j++)

{

sc[j]=0;

}

int k=0;

for(int i =0;i<=a;i++)

{

if(sc[i]==1)

{

k++;

}

printf("%d\n",k);

return 0;

}

发表于 2025-10-09 18:56:56 回复(0)

Java

duckyal

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int L = in.nextInt(), M = in.nextInt();
        StringBuffer sb = new StringBuffer();
        sb.setLength(L+1);
        for (int n=0; n<M; n++) {
            int l = in.nextInt(), r = in.nextInt();
            for (int t=l; t<=r; t++) {
                sb.setCharAt(t, '0');
            }
        }
        System.out.println(sb.toString().replaceAll("0", "").length());
    }
}

依旧StringBuffer

发表于 2025-10-09 10:53:59 回复(0)

提交观点

问题信息

NOIP复赛枚举

难度：

38条回答 246收藏 1158浏览

通过挑战的用户

查看代码

全马破三

2022-12-28 13:14:38
WaterYi

2022-11-23 10:16:32
Wilson_...

2022-11-17 21:20:06
Acmer-ly

2022-04-04 16:29:20
多多捞捞菜菜

2022-03-21 14:06:43

校门外的树

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题