校门外的树
区间移树，统计剩余树数
正文
// 原题：https://oj.yecheng.tv/p/1397
// 题意：0..l 每整点一棵树，m 个区间的树移走（含端点），求剩余树数。
// 思路：布尔数组标记被移走的树，统计未被标记的。
// 复杂度：O(l + m * 区间长)。
// 易错点：树在 0..l 共 l+1 棵；区间端点处的树也算移走。
#include <iostream>
using namespace std;
int main(){
int l, m, u, v, tree[10005] = {0}, ans = 0;
cin >> l >> m;
for(int i = 0; i < m; i++){
cin >> u >> v;
for(int j = u; j <= v; j++) tree[j] = 1;
}
for(int i = 0; i <= l; i++) if(!tree[i]) ans++;
cout << ans << endl;
return 0;
}
洛谷·深入浅出的其它内容
- 简单的分苹果
- 简单的分苹果 2
- 圆的计算
- 简单的猴子吃桃
- 评测机队列
- 面积计算
- 竞赛得分
- 简单的分苹果 3
- 鸡兔共笼
- 定期存款
- 跑步
- 英文字母
- 玩橡皮泥
- 销量预测
- 苹果采购
- 字母转换
- 数字反转
- 再分肥宅水
- 小鱼的游泳时间
- 成绩
- 上学迟到
- 三角形面积
- 小玉买文具
- 苹果和虫子
- 对角线
- 数字比较
- 数的性质
- 闰年判断
- Apples
- 洛谷团队系统
- 肥胖问题
- 三位数排序
- 月份天数
- 不高兴的津津
- 买铅笔
- 三角形分类
- 小玉家的电费
- 小鱼的航程（改进版）
- 三角函数
- 陶陶摘苹果
- [COCI2006-2007#2] ABC
- 找最小值
- 分类平均
- 一尺之棰
- 数字直角三角形
- 阶乘之和
- 计数问题
- 级数求和
- 金币
- 数列求和
- 质数口袋
- 回文质数 Prime Palindromes
- 小玉在游泳
- 数字反转
- 月落乌啼算钱（斐波那契数列）
- 求极差 / 最大跨度值
- 最长连号
- 质因数分解
- 求三角形
- 打分