首页 > 试题广场 >

剩下的树

[编程题]剩下的树

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

有一个长度为整数L(1<=L<=10000)的马路，可以想象成数轴上长度为L的一个线段，起点是坐标原点，在每个整数坐标点有一棵树，即在0,1,2，...，L共L+1个位置上有L+1棵树。现在要移走一些树，移走的树的区间用一对数字表示，如 100 200表示移走从100到200之间（包括端点）所有的树。可能有M(1<=M<=100)个区间，区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。

输入描述:

    两个整数L(1<=L<=10000)和M(1<=M<=100)。
    接下来有M组整数，每组有一对数字。

输出描述:

    可能有多组输入数据，对于每组输入数据，输出一个数，表示移走所有区间的树之后剩下的树的个数。

示例1

输入

输出

算法知识视频讲解

Java

早豆浆晚牛奶

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while ((s = br.readLine()) != null) {
            String[] ss = s.split(" ");
            int L = Integer.parseInt(ss[0]);
            int M = Integer.parseInt(ss[1]);
            int[] way = new int[L+1];
            Arrays.fill(way, 1);//默认种满了树
            for (int i = 0; i < M; i++) {
                String[] str = br.readLine().split(" ");
                int start = Integer.parseInt(str[0]);
                int end = Integer.parseInt(str[1]);
                for (int j = start; j <= end; j++) {
                    way[j] = 0;
                }
            }
            int cout = 0;
            for (int i = 0; i < L+1; i++) {
                if (way[i] != 0) cout++;
            }
            System.out.println(cout);

        }

    }

}

发表于 2021-04-21 16:16:50 回复(0)

Java

LHC0512

Java 解法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int l = scanner.nextInt();
        int m = scanner.nextInt();
        int[] record = new int[l + 1];
        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            for (int j = x; j <=y ; j++) {
                record[j]=1;
            }
        }
        int count=0;
        for (int i = 0; i <= l; i++) {
            if (record[i]==0)
                count++;
        }
        System.out.println(count);
    }
}

发表于 2020-03-07 21:53:18 回复(0)

Java

/xinCupid☆

区间覆盖问题

import java.util.*;
class Interval implements Comparable<Interval> {
    private int start;
    private int end;
    
    public Interval(int s, int e) {
        start = s;
        end = e;
    }
    public int getStart() {
        return start;
    }
    public int getEnd() {
        return end;
    }
    
    public int compareTo(Interval other) {
        if (start == other.start) {
            return end - other.end;
        }
        return start - other.start;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        while (reader.hasNext()) {
            ArrayList<Interval> intervals = new ArrayList<>();
            int L = reader.nextInt();
            int M = reader.nextInt();
            for (int i = 0; i < M; ++i) {
                int start = reader.nextInt();
                int end = reader.nextInt();
                intervals.add(new Interval(start, end));
            }
            Collections.sort(intervals);
            int prev_end = intervals.get(0).getEnd();
            int prev_start = intervals.get(0).getStart();
            int sum = prev_end - prev_start;
            for (int i = 1; i < intervals.size(); ++i) {
                if (intervals.get(i).getStart() < prev_end) {
                    if (intervals.get(i).getEnd() > prev_end) {
                        sum += intervals.get(i).getEnd() - prev_end;
                    }
                } else {
                    sum += intervals.get(i).getEnd() - intervals.get(i).getStart() + 1;
                }
                prev_end = Math.max(intervals.get(i).getEnd(), prev_end);
            }
            System.out.println(L - sum);
        }
    }
}

发表于 2018-03-29 20:50:36 回复(0)