[已解决]植树问题

柿子饼同学

题目描述
某校大门外长度为 ll 的马路上有一排树，每两棵相邻的树之间的间隔都是 11 米。我们可以把马路看成一个数轴，马路的一端在数轴 00 的位置，另一端在 ll 的位置；数轴上的每个整数点，即 0,1,2,\dots,l0,1,2,…,l，都种有一棵树。

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

输入格式
第一行有两个整数，分别表示马路的长度 ll 和区域的数目 mm。

接下来 mm 行，每行两个整数 u, vu,v，表示一个区域的起始点和终止点的坐标。

输出格式
输出一行一个整数，表示将这些树都移走后，马路上剩余的树木数量。

输入输出样例
输入 #1 复制
500 3
150 300
100 200
470 471
输出 #1 复制
298
说明/提示
【数据范围】

对于 20\%20% 的数据，保证区域之间没有重合的部分。
对于 100\%100% 的数据，保证 1 \leq l \leq 10^41≤l≤10
4
，1 \leq m \leq 1001≤m≤100，0 \leq u \leq v \leq l0≤u≤v≤l。
【题目来源】

NOIP 2005 普及组第二题

题目如上， 下面是我写的代码 ，感觉跟题解相差不大，为什么答案错误呢

#include <bits/stdc++.h>
using namespace std;
int main(){
        int l, m, u, v, s=0;
        vector<int> tree(10001, 1);
        scanf("%d%d", &l, &m);
        for(int i = 0; i <= m; i++){
                scanf("%d%d", &u, &v);
                for(i=u; i<=v; i++){
                        tree[i] = 0;
                }
        }
        for(int i=0; i<l; i++){
                if(tree[i] == 1){
                        s++;
                }
        }
        printf("%d", s);
        return 0;
}

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-3-7 13:48:06

不知道是不是我手机问题，看不到自己的回复（重发）
思路和你一样，只是树数量不同：

#include <iostream>
#include <vector>

int main(){
        int l, m, a, b, sum = 0;
        std::cin >> l >> m; // 终点、区域数量
        std::vector<int> trees(l + 1, 1);
        for(int i = 0; i < m; i++){
                std::cin >> a >> b;
                for(int j = a; j < b+1; j++) trees[j] = 0;
        }
        for(int x: trees) if(x) sum++;
        std::cout << sum << std::endl;
        return 0;
}

跳转到最佳答案楼层

傻眼貓咪

不知道是不是我手机问题，看不到自己的回复（重发）
思路和你一样，只是树数量不同：

#include <iostream>
#include <vector>

int main(){
        int l, m, a, b, sum = 0;
        std::cin >> l >> m; // 终点、区域数量
        std::vector<int> trees(l + 1, 1);
        for(int i = 0; i < m; i++){
                std::cin >> a >> b;
                for(int j = a; j < b+1; j++) trees[j] = 0;
        }
        for(int x: trees) if(x) sum++;
        std::cout << sum << std::endl;
        return 0;
}

jhq999

每两棵相邻的树之间的间隔都是 11 米，怎么没体现出来？

int main(){
        int l, m, u, v, s=0;
        vector<int> tree(10001, 1);
        scanf("%d%d", &l, &m);
        for(int i = 0; i < m; i++){/////////////////
                scanf("%d%d", &u, &v);
                for(int j=u; j<=v; j++){/////////////////
                        tree[j] = 0;
                }
        }
        for(int i=0; i<l; i++){
                if(tree[i] == 1){
                        s++;
                }
        }
                if (tree[0])////////////////////
                {
                        s++;
                }
        printf("%d", s);
        return 0;
}

柿子饼同学

jhq999 发表于 2022-3-7 17:21
每两棵相邻的树之间的间隔都是 11 米，怎么没体现出来？

嘶 , 不好意思 , 当时在学校里复制的可能没仔细检查 , 网站问题多弄了一个1...
不过 , 您的程序我会借鉴学习的
谢谢回答~

柿子饼同学

jhq999 发表于 2022-3-7 17:21
每两棵相邻的树之间的间隔都是 11 米，怎么没体现出来？

后面我发网址吧