|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
题目描述
某校大门外长度为 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;
- }
不知道是不是我手机问题，看不到自己的回复（重发）
思路和你一样，只是树数量不同： - #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;
- }
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-3-7 13:24:55
置顶卡
千斤顶
显身卡
发表于 2022-3-7 13:48:06
楼主