首页 > 试题广场 >

校门外的树

[编程题]校门外的树

热度指数：6487 时间限制：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] 有  棵被重复移除，所以实际移除  棵，剩余  棵。

备注:

算法知识视频讲解

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)

Java