← 返回题目
题库练习 信息学奥赛练习题：种树【
← 上一题 下一题 →

A62053 | 信息学奥赛练习题：种树【

来源2023年
时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

信息学奥赛练习题：种树

【题目描述】

现在我们国家开展新农村建设，农村的住房建设纳入了统一规划，统一建设，政府要求每一住户门口种些树。门口路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民房子门前被指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量，尽量较少政府的支出。

 

【输入】

第一行包含数据N，M，区域的个数(0<N≤30000)，房子的数目(0<m≤5000)；

 

下面的m行描述居民们的需要：B E T，0<B≤E≤30000，T≤E-B+1。

 

【输出】

输出一个数，为满足所有居民的要求，所需要种树的最少数量。

 

【输入样例】

9 4

3 5 2

1 4 2

4 6 2

8 9 2

【输出样例】

5

C++ 编辑器
输入
输出