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

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

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

【题目描述】

大雨过后,从小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

【题目分析】

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


  • 需要考虑



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

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

分享给朋友:

相关文章

【题解】核电站问题

【题目描述】一个核电站有N个放核物质的坑,坑排列在一条直线上。如果连续3个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。现在,请你计算:对于给定的N,求不发生爆炸的放置核物质的方案总数...

【题解】装满杯子需要的最短总时长

【题目描述】现有一台饮水机,可以制备冷水、温水和热水。每秒钟,可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。给你一个下标从&nb...

【题解】2019 T2 公交换乘

【题目描述】著名旅游城市 B 市为了鼓励大家采用公共交通方式出行,推出了一种地铁换乘公交车的优惠方案:1、在搭乘一次地铁后可以获得一张优惠票,有效期为 45 分钟,在有效期内可以消耗这张优惠...

【题解】公式成绩

【题目描述】学校的期中考试到了。 gp 老师一共收集到 n 个学生的成绩,每个学生有 5 科成绩,分别是语文、数学、英语、政治、历史。(ai,bi,ci,di,ei) gp 老师突发奇想,他用 m...

【题解】苯小猴

【题目描述】笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!这种方法的具体描述如下:假设maxn是单词中出现次数最...

【题解】阳光

【题目描述】给出一个n*n的矩阵,矩阵每个元素数值代表这个位置的阳光情况,给出正整数k,需要我们求出哪一处的k*k 区域的阳光平均值最多,阳光平均值为k*k 区域的阳光总和除于k*k。蒜头君想让我们输...