首页 > 试题广场 >

校门外的树

[编程题]校门外的树

热度指数：18587 时间限制：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())
nums = [1] * (l + 1)
for _ in range(m):
    left, right = map(int, input().split())
    nums[left:right+1] = [0] * (right - left + 1)
print(sum(nums))

发表于 2026-01-16 15:44:19 回复(0)

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)

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)

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)

L1LL

/*
 * 容斥原理
 * 方法原理：利用容斥原理计算多个区间的并集大小（奇加偶减规则），总树数减去并集大小得到剩余数量；
 *          通过格雷码遍历区间子集，避免重复计算重叠区域的树的数量。
 * 时间复杂度：O(M×2^M)
 * 空间复杂度：O(M)
 * 适用场景：L极大（如1e9）、M极小（≤15）的场景（无法开辟大数组存储标记）
 */
#include <stdio.h>

int main() {
    int L, M;
    if (scanf("%d %d", &L, &M) != 2 || L < 1 || L > 10000 || M < 1 || M > 100) {
        return 1;
    }
    // 总树数（0~L共L+1棵）
    int T = L + 1;
    // ls/rs存储各砍伐区间的左右端点，p用于格雷码遍历子集
    int ls[100], rs[100], p = 1;
    // 遍历每个砍伐区间
    for (int i = 0; i < M; i += 1) {
        int l, r;
        if (scanf("%d %d", &l, &r) != 2 || 0 > l || l > r || r > L) {
            return 1;
        }
        // 先减去当前区间的树数（假设无重叠）
        T -= r - l + 1;
        // 保存当前区间端点
        ls[i] = l;
        rs[i] = r;

        // 容斥原理核心：遍历前i个区间的所有非空子集，修正重叠区域的重复减法
        for (int j = 1; j < p; j += 1) {
            // lc/rc暂存当前子集与当前区间的交集端点
            int lc = l, rc = r;
            // 格雷码转换：j ^ (j>>1) 高效遍历所有子集
            for (int g = j ^ (j >> 1), k = 0; g > 0 && k < i; k += 1, g /= 2) {
                if (g % 2 == 1) {
                    // 计算交集：左端点取大，右端点取小
                    if (lc < ls[k]) {
                        lc = ls[k];
                    }
                    if (rc > rs[k]) {
                        rc = rs[k];
                    }
                    // 无交集则退出当前子集计算
                    if (rc < lc) {
                        break;
                    }
                }
            }
            // 有交集时，按子集大小奇偶性调整（奇加偶减）
            if (rc >= lc) {
                if (j % 2 == 1) {
                    T += rc - lc + 1; // 奇数子集：补回重复减去的交集
                } else {
                    T -= rc - lc + 1; // 偶数子集：再减去多补的部分
                }
            }
        }
        // p翻倍，为下一次遍历所有子集做准备
        p *= 2;
    }
    printf("%d", T);
    return 0;
}

/*
 * 数组标记
 * 方法原理：用数组标记树的状态（0=未砍伐/-1=被砍伐），通过memset批量标记砍伐区间；
 *          最后累加数组值统计剩余未砍伐树的数量（0不影响，-1则总数量减1）。
 * 时间复杂度：O(L+M)
 * 空间复杂度：O(L)
 * 适用场景：L适中（≤1e4）、追求代码简洁性的场景，新手易理解
 */
#include <stdio.h>
#include <string.h>

int main() {
    int L,M;
    if (scanf("%d %d", &L, &M) != 2 || L < 1 || L > 10000 || M < 1 || M > 100) {
        return 1;
    }
    // 总树数（0~L共L+1棵）
    int T = L + 1;
    // t数组：标记树的状态（0=未砍伐，-1=被砍伐）
    int t[T];
    // 初始化：所有树未被砍伐
    for (int i = 0; i < T; i += 1) {
        t[i] = 0;
    }
    // 遍历所有砍伐区间，批量标记被砍伐的树
    for (int i = 0; i < M; i += 1) {
        int l, r;
        if (scanf("%d %d", &l, &r) != 2 || 0 > l || l > r || r > L) {
            return 1;
        }
        // memset按字节赋值：0xff对应int的-1，4*(r-l+1)是区间总字节数（int占4字节）
        // 批量将t[l]~t[r]设为-1（标记为被砍伐）
        memset(t + l, 0xff, 4 * (r - l + 1));
    }
    // 统计剩余树数：未砍伐（+0），被砍伐（-1）
    for (int i = 0; i <= L; i += 1) {
        T += t[i];
    }
    printf("%d", T);
    return 0;
}

/*
 * 跳跃标记
 * 方法原理：通过数组标记每个位置的“下一个未被砍伐的位置”，初始化后遍历砍伐区间完成标记；
 *          再跳跃式遍历标记数组，快速计算剩余未砍伐树的数量，避免重复遍历已标记区间。
 * 时间复杂度：O(L+M)
 * 空间复杂度：O(L)
 * 适用场景：L适中（≤1e4）、M任意的常规场景，效率高且逻辑直观
 */
#include <stdio.h>

int main() {
    int L,M;
    if (scanf("%d %d", &L, &M) != 2 || L < 1 || L > 10000 || M < 1 || M > 100) {
        return 1;
    }
    // 总树数（0~L共L+1棵）
    int T = L + 1;
    // R数组：标记每个位置的「下一个未被砍伐的位置」
    int R[T + 1];
    // 初始化：所有位置未被砍伐，下一个未砍伐位置为自身
    for (int i = 0; i <= T; i += 1) {
        R[i] = i;
    }
    // 遍历所有砍伐区间，完成标记
    for (int i = 0; i < M; i += 1) {
        int l, r;
        if (scanf("%d %d", &l, &r) != 2 || 0 > l || l > r || r > L) {
            return 1;
        }
        // 优化：避免重复标记已处理的区间
        if (r + 1 > R[l]) {
            // 标记[l, r]区间：所有位置的下一个未砍伐位置设为r+1
            for (int i = l; i < r + 1; i += 1) {
                R[i] = r + 1;
                printf("R[%d]=%d\n", i, R[i]);
            }
        }
    }
    // 跳跃遍历：快速计算剩余未砍伐树的数量
    int i = 0;
    while (i <= L) {
        // 找到第一个被砍伐的位置（R[i]≠i）
        for (; i <= L; i += 1) {
            if (i != R[i]) {
                printf("i=%d R[i]=%d\n", i, R[i]);
                break;
            }
        }
        // 减去当前被砍伐区间的长度，然后跳到区间终点继续遍历
        T -= R[i] - i;
        printf("T=%d\n", T);
        i = R[i];
    }
    printf("%d", T);
    return 0;
}

/*
 * 区间合并
 * 方法原理：先通过插入排序将所有砍伐区间按左端点升序排列，再遍历合并重叠/包含区间；
 *          仅计算实际被砍伐的总长度（避免重复减重叠区域），总树数减去该长度得到剩余数量。
 * 时间复杂度：O(M²+M)
 * 空间复杂度：O(M)
 * 适用场景：L极大（如1e9）、M适中（≤1000）的场景，无大数组内存压力
 */
#include <stdio.h>

int main() {
    int L,M;
    if (scanf("%d %d", &L, &M) != 2 || L < 1 || L > 10000 || M < 1 || M > 100) {
        return 1;
    }
    // 总树数（0~L共L+1棵）
    int T = L + 1;
    // ls/rs存储区间的左右端点
    int ls[M], rs[M];
    // 读取区间并插入排序（按左端点升序），为合并区间做准备
    for (int i = 0; i < M; i += 1) {
        int l, r;
        if (scanf("%d %d", &l, &r) != 2 || 0 > l || l > r || r > L) {
            return 1;
        }
        // 插入排序核心：将当前区间插入到已排序的位置
        int j = i - 1;
        // 向前遍历已排序区间，左端点更小则后移区间
        while (j >= 0 && l < ls[j]) {
            ls[j + 1] = ls[j];
            rs[j + 1] = rs[j];
            j -= 1;
        }
        // 将当前区间插入到正确位置
        ls[j + 1] = l;
        rs[j + 1] = r;
    }
    // 合并区间：R为当前合并区间的右端点（初始为第一个区间的右端点）
    int R = *rs;
    // 先减去第一个区间的长度
    T -= R - *ls + 1;
    // 遍历剩余区间，合并重叠/包含区间
    for (int i = 1; i < M; i += 1) {
        // 情况1：区间重叠且右端点超出当前合并区间 → 只减超出部分
        if (ls[i] <= R && rs[i] > R) {
            T -= rs[i] - R;
            R = rs[i]; // 更新合并区间右端点
        }
        // 情况2：区间无重叠 → 减去整个区间长度
        else if (ls[i] > R) {
            T -= rs[i] - ls[i] + 1;
            R = rs[i]; // 更新合并区间右端点
        }
        // 情况3：区间被包含 → 无需处理（避免重复减）
    }
    printf("%d", T);
    return 0;
}

发表于 2026-01-09 13:59:16 回复(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)

Sun_Hook

这一题的算法很多，可以暴力求解，也可以差分算法，可以区间合并，复杂度不一样。

发表于 2026-04-16 18:43:48 回复(0)

C++

STTZDW

#include <iostream>

#include <vector>

using namespace std;

int main() {

int a, b,l,m,f,count=0;

cin>>l>>m;

vector<int>lu(l);

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

cin>>f>>b;

for (int j=f; j<b+1; j++) {

if (lu[j]==0) {

lu[j]=1;

count++;

}

cout<<lu.size()+1-count;

}

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

发表于 2026-03-31 20:22:45 回复(0)

牛客469593752号

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

l=list(range(a+1))

for i in range(b):

c,d=map(int,input().split())

for c in range(c,d+1):

l[c]=-1

print(a+1-l.count(-1))

发表于 2026-03-31 14:14:41 回复(0)

C++

Fskn0804

#include <iostream>

using namespace std;

bool road[10001]; // 用布尔值来表示树是否还存在

int main() {

int L,M;

cin>>L>>M;

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

road[i]=true; // 初始所有树都是存在状态

}

int l,r;

while (M--){

cin>>l>>r;

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

road[j]=false; // 遍历所有施工区域，里面的树都被移走，也就不存在了

}

int cnt=0;

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

if (road[i]){

cnt++; // 再次遍历整条路，统计还存在的树的数量

}

cout<<cnt;

return 0;

}

发表于 2026-03-30 11:26:54 回复(0)

在摸鱼的加菲猫

#include<stdio.h>

int main()

{

int L,M;

scanf("%d%d",&L,&M);

int tree[100001]={0};

int l,r;

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

{

scanf("%d%d",&l,&r);

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

{

tree[j]=1;

}

int count=0;

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

{

if(tree[i]==0) count++;

}

printf("%d",count);

return 0;

}

发表于 2026-03-28 11:41:00 回复(0)

蜜雪儿11

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int total = in.nextInt();

int n = in.nextInt();

boolean[] trees = new boolean[total + 1];

// 记录每米树的状态，初始为true表示有树

Arrays.fill(trees, true);

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

int start = in.nextInt();

int end = in.nextInt();

for (int j = start; j <= end; j++) {

trees[j] = false; // 移除该区域的树

}

in.close();

int count = 0;

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

if (trees[i]) {

count++;

}

System.out.println(count);

}

发表于 2026-03-15 18:18:52 回复(0)

Python3

想要offer的马来熊很爱喝奶茶

import sys

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

list1 = list(range(L + 1))

list2 = []

for line in sys.stdin:

a = line.split()

list2 = [i for i in range(int(a[0]), int(a[-1]) + 1)] + list2

list3 = list(set(list2))

for i in list3:

list1.remove(i)

print(len(list1))

发表于 2026-03-13 19:50:49 回复(0)

C++

牛客517463444号

#include<bits/stdc++.h>

using namespace std;

bool cmp(pair<int,int> &a,pair<int,int>&b){

return a.first<b.first;

}//自定义比较函数

int main() {

int l,m;

int a,b;

cin>>l>>m;

vector<pair<int,int>>arr;

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

cin>>a>>b;

arr.push_back({a,b});

}

sort(arr.begin(),arr.end(),cmp);

for(int i=1;i<arr.size();){//合并区间

if(arr[i].first<arr[i-1].second){

if(arr[i].second<arr[i-1].second){

arr.erase(arr.begin()+i);

continue;

}

else{

arr[i-1].second=arr[i].second;

arr.erase(arr.begin()+i);

continue;

}

i++;

}

int sum=0;

for(auto it:arr)

sum=sum+it.second-it.first+1;

cout<<l-sum+1;

}

发表于 2026-03-05 16:38:10 回复(0)

Java

cmhYaChiXiaoLe

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //马路长度L
        int l = in.nextInt();
        //施工区域M
        int m = in.nextInt();
        //我的思路是遍历数组，把移除树状态置为-1，最后统计非-1的数
        //初始化501棵树
        int[] treeArray = new int[l + 1];
        for (int i = 0; i < l + 1; i++) {
            treeArray[i] = i;
        }
        //遍历施工区域，移除树（我这里思路是：标记移除位）
        for (int i = 1; i <= m; i++) {
            int start =
                in.nextInt(); //注意包含两端，所以数组范围是[start,end]
            int end = in.nextInt();
            for (int k = 0; k < l + 1; k++) {
                if (treeArray[k] >= start && treeArray[k] <= end) {
                    treeArray[k] = -1;
                }
            }
        }
        //统计未标记的树
        int remaining = 0;
        for (int i = 0; i < l + 1; i++) {
            if (treeArray[i] != -1) {
                remaining++;
            }
        }
        System.out.println(remaining);

    }
}

发表于 2026-02-26 10:54:39 回复(1)

whisper_trap

#include<bits/stdc++.h>

using namespace std;

int main(){

int L , M;

cin >> L >>M;

int step = 0;

int tree[10005] = {1};//树存在为1，移除为0

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

tree[i] = 1;

}

while (M--) {

int l , r;

cin >> l >> r;

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

if (tree[l + i] == 1) {

tree[l + i] = 0;

}

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

if (tree[j] == 1) {

step++;

}

cout << step<<endl;

}

发表于 2026-02-08 15:08:58 回复(0)

小蔡驾到

#include <stdio.h>

#include <stdlib.h>

int main() {

int L,M;

scanf("%d %d",&L,&M);

int *arr=(int*)malloc(L*sizeof(int));

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

arr[i]=1;//初始化树全在

}

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

int m,n;

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

for(int k=m;k<=n;k++){

arr[k]=0;//区间内的树移除

}

int len=0;

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

if(arr[q]==1){

len++;

}

}//计算最终1的个数就是树的个数。这样不用考虑复杂的重合区间问题

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

return 0;

}

发表于 2026-02-06 17:08:17 回复(0)

C++

喜欢后撤步的小太阳等一个offer

序列原来还能这样初始化

#include <bits/stdc++.h>

using namespace std;

int main() {

int L,M,max,min,i,cnt=0;

cin>>L>>M;

vector <int> num(L+1,0);

while(M--){

int a,b;

cin>>a>>b;

for(i=a;i<=b;i++){

num[i]=-1;

}

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

if(num[i]>=0)

cnt++;

}

cout<<cnt;

}

发表于 2026-01-25 19:45:41 回复(0)

提交观点

问题信息

NOIP复赛枚举

难度：

57条回答 341收藏 2499浏览

通过挑战的用户

查看代码

全马破三

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

校门外的树

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题