首页 > 试题广场 >

校门外的树

[编程题]校门外的树

热度指数：6427 时间限制：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)

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)

吴坤桓

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)

C++

呼唤cube

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

int main() {
    int l,m;
    cin >> l >> m;
    vector<bool>tree(l+1,true);
    while(m--){
        int beginnum,endnum;
        cin >> beginnum >> endnum;
        //完全的笨办法，把所有给出的区间都置0
        for(;beginnum <= endnum;beginnum++){
            tree[beginnum] = false;
        }
    }
    //然后统计剩下了多少1
    int count = 0;
    for(int i = 0 ; i <= l ; i++){
        if(tree[i])count++;
    }
    cout << count <<endl;
    return 0;
}

发表于 2025-10-05 17:53:37 回复(0)

八重神子胡大牌

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

发表于 2025-09-24 14:29:21 回复(0)

我腿短先溜了ing

我这里只用到了之前学过的概念前缀和。然后看到各位大佬用到的差分数组结合前缀和，针对于重复计算区间处理真的很赞，又学到了
def solution():

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

L1 = list(range(0,L+1))

prefix = [0]*(L+1)

for i in range(M):

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

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

prefix[j] = True

print(prefix.count(0))

solution()

发表于 2025-09-17 00:45:11 回复(0)

牛客315087695号

使用布尔数组先将所有的树设为False 如果需要拔出则修改为True 如果已经在之前的遍历中确认要拔出则保持最后还是False的就是要保留的树

import sys

L=0

M=0

for line in sys.stdin:

if L==0 and M==0 :

a = line.split()

L=int(a[0])+1

M=int(a[1])

road=[False]*L

continue

else:

a =list(map(int,line.split()))

for i in range(a[1]+1)[a[0]:]:

if road[i]==False:

road[i]=True

M-=1

if M==0:

print(road.count(False))

T=0

发表于 2025-08-30 14:49:22 回复(0)

C++

牛客874874800号

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

// 输入马路长度L和区域数量M

int L, M;

cin >> L >> M;

// 存储每个区域的起止区间

vector<pair<int, int>> intervals;

// 读取M个区域的起止点

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

int l, r;

cin >> l >> r;

intervals.push_back(make_pair(l, r)); // 保存区间

}

// 按区间起点升序排序

sort(intervals.begin(), intervals.end(), [](const pair<int, int>& a, const pair<int, int>& b) {

return a.first < b.first; // 按起点比较

});

// 合并重叠区间

vector<pair<int, int>> merged;

if (!intervals.empty()) {

int curStart = intervals[0].first; // 当前合并区间的起点

int curEnd = intervals[0].second; // 当前合并区间的终点

for (int i = 1; i < intervals.size(); i++) {

// 如果当前区间与前一个区间重叠或相邻

if (intervals[i].first <= curEnd + 1) {

// 扩展当前合并区间到两个区间的最大终点

curEnd = max(curEnd, intervals[i].second);

} else {

// 保存当前合并的区间，开始新的合并区间

merged.push_back(make_pair(curStart, curEnd));

curStart = intervals[i].first;

curEnd = intervals[i].second;

}

// 保存最后一个合并的区间

merged.push_back(make_pair(curStart, curEnd));

}

// 计算所有合并区间覆盖的总树数

int totalRemoved = 0;

for (const auto& seg : merged) {

// 区间内树的数量 = 终点 - 起点 + 1

totalRemoved += (seg.second - seg.first + 1);

}

// 计算并输出剩余的树数

// 马路上总树数 = L + 1 (从0到L)

int remainingTrees = (L + 1) - totalRemoved;

cout << remainingTrees;

return 0;

}

发表于 2025-08-20 15:03:18 回复(0)

Nitrene

#include<bits/stdc++.h>

using namespace std;

int main(){

int L,M,n,a[100000]={0};

cin>>L>>M;

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

int l,r;

cin>>l>>r;

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

if(a[j] == 0) {

a[j] = 1;

L--;

}

cout<<L+1<<endl;

return 0;

}

发表于 2025-08-12 17:53:33 回复(0)

牛客808550497号

using System;

public class Program {

public static void Main() {

string[] input =Console.ReadLine().Split();

int L = int.Parse(input[0]);

int M = int.Parse(input[1]);

//创建长度为L+1的bool数组trees，创建一个布尔数组 trees 来记录每个位置是否有树。

bool[] trees = new bool[L+1];

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

trees[i]=true;

}

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

string[] region = Console.ReadLine().Split();

int left = int.Parse(region[0]);

int right = int.Parse(region[1]);

for(int j=left;j<=right;j++){

trees[j]=false;

}

int count=0;

foreach(bool exists in trees){

if (exists){

count++;

}

Console.WriteLine(count);

}

发表于 2025-07-31 20:46:24 回复(0)

肖顶天

类似于标记法，将所用存在的树标记为true，不存在的树标记为false最后遍历整个数组，统计还存在的树

#include <iostream>

#include <vector>

using namespace std;

int main() {

int L,M;

cin>>L>>M;

vector<bool> trees(L+1,true);

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

{

int l,r;

cin>>l>>r;

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

{

trees[j]=false;

}

int remain_trees=0;

for(bool tree:trees)

{

if(tree)

{

remain_trees++;

}

cout<<remain_trees<<endl;

}

// 64 位输出请用 printf("%lld")

发表于 2025-07-30 17:32:56 回复(0)

Java

艾斯卡

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int L = in.nextInt();

int M = in.nextInt();

//用数组来接被铲掉的树，这样就可以避免重复的树被计算了

boolean[] treeOut = new boolean[L+1];

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

int a=in.nextInt();

int b=in.nextInt();

for(int j=a;j<=b;j++){

treeOut[j]=true;

}

//计数没有被铲掉的树

int count =0;

for(int k = 0;k<=L;k++){

if(!treeOut[k]){

count++;

}

System.out.print(count);

}

发表于 2025-07-29 17:02:37 回复(0)

Python3

牛客940035856号

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

#马路所有的树

n = [i for i in range(l+1)]

for j in range(m):

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

#区域中的树

nl = [y for y in range(l1,r+1)]

for x in nl:

if x in n:

n.remove(x)

else:

pass

print(len(n))

复杂度比较高

发表于 2025-07-21 15:22:06 回复(0)

在许愿的菠萝蜜很不想泡池子

#include <stdio.h>

void shu(int a[],int l,int r,int L)
{
    for(int i=0;i<=L;i++)
    {
        if(i>=l&&i<=r)
        {
            a[i]=1;
        }
    }
}
int main() {
    int L,M;
    scanf("%d%d",&L,&M);
    int a[10000]={0};
    int n=M;
    for(int i=0;i<n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        shu(a,l,r,L);
    }
    int hen=0;
    for(int i=0;i<=L;i++)
    {
        if(a[i]==0)
        {
            hen++;
        }
    }
    printf("%d",hen);
}

发表于 2025-07-17 19:35:23 回复(0)

提交观点

问题信息

NOIP复赛枚举

难度：

27条回答 174收藏 623浏览

通过挑战的用户

查看代码

全马破三

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

校门外的树

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题