当前位置:首页 > 题解目录 > 正文内容

【题解】泥泞路(2019青岛市程序设计竞赛)

亿万年的星光4年前 (2021-04-16)题解目录2437

【题目描述】

大雨过后,从小A的农场到镇上的公路上有一些泥泞路段,为了方便出行,他决定将若干块长度为L的木板可以铺在这些泥泞路段上,问他至少需要多少块木板,才能将所有的泥泞路段覆盖住。

【输入】

第一行为正整数n(n≤10000)和L(L≤10000),分别表示有多少段泥泞路和木板的长度;接下来n行,每一行两个整数s和e(s≤e≤109),表示每一段泥泞路的起点和终点。

【输出】

仅一个正整数,表示使用的木板数。

【输出】

仅一个正整数,表示木板数。

【样例输入输出】

cover.in

cover.out

3 3

1 6

13 17

8 12

5

 

【数据范围】

60%的数据:n<=1000;

100%的数据:n<=100000,L<=10000, s≤e≤109

【来源】

2019年青岛市程序设计竞赛试题(初中组)3T

【题目分析】

  • 属于区间覆盖类问题,但是题目中有些地方描述的不够清楚。


  • 需要考虑



扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】Crossing River

【题目描述】几个人过河,每次过两人一人回,速度由慢者决定,问过河所需最短时间。【输入描述】输入t组数据,每组数据第1行输入n,第2行输入n个数,表示每个人过河的时间。【输出描述】输出t行数据,每行1个...

合影效果

【题目描述】小云和朋友们去爬香山,为美丽的景色所陶醉,想合影留念。如果他们站成一排,男生全部在左(从拍照者的角度),并按照从矮到高的顺序从左到右排,女生全部在右,并按照从高到矮的顺序从左到右排,请问他...

连词成句

【题目描述】有一天,毛毛上课的时候遇到了一个难题,老师让同学们把黑板上的单词连成一句话。已知连词的规则是:从待选词中选出正确的单词按照顺序输出,“正确的单词”表示除第一个单词外,其余单词都是小写字母,...

【题解】幸运儿

【题目描述】n 个人围成一圈, 并依次编号1~n,从编号为1 的人开始,按顺时针方向每隔一人选出一个,当一圈结束之后,剩下的人重新围成一圈,再次从编号1的人开始,如此循环直到剩下两人,这剩下的两人就是...

植树节

【题目描述】植树节快要到了,学校要组织志愿者去给树苗浇水。有一排树苗,编号依次是 0,1,2, . . . 。现有 n个志愿者去给树苗浇水,第 i 个志愿者选定了一个区间[ai, bi],表示第 i个...

生日

【题目描述】cjf君想调查学校OI组每个同学的生日,并按照从大到小的顺序排序。但cjf君最近作业很多,没有时间,所以请你帮她排序。【输入描述】有2行,第1行为OI组总人数n;第2行至第n+1行分别是每...