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

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

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

【题目描述】

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

【题目分析】

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


  • 需要考虑



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

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

分享给朋友:

相关文章

【题解】切割钢管

【题解】切割钢管

【题目描述】小A是某工地的计算工程师。工地现有 n 根钢管,第 i 根钢管的长度为 ai。现在想用这 n 根钢管来做一个支撑用的柱子。我么可以切割这些钢管成为更短的钢管,但是不能缝合两根钢管。为了安全...

因子分解

【题目描述】输入一个数,输出其素因子分解表达式。【输入描述】输入一个整数 n (2≤n<100)。【输出描述】输出该整数的因子分解表达式。表达式中各个素数从小到大排列。如果该整数可以分解出因子a...

【题解】取数

【题目描述】设有N 个正整数(1 <= N <= 50),其中每一个均是大于等于1、小于等于300的数。从这N个数中任取出若干个数(不能取相邻的数),要求得到一种取法,使得到的和为最大。例...

公路(road)

公路(road)

【题目描述】小苞准备开着车沿着公路自驾。公路上一共有n个站点,编号为从1 到n。其中站点i与站点i+1 的距离为vi公里。公路上每个站点都可以加油,编号为i 的站点一升油的价格为a...

【题解】AC

4.AC(ac.cpp) 【问题描述】 小明获得了一行字符串,他想知道在不改变字符顺序的情况下,从前到后最多能组合出多少个ac? (a和c的位置可以不连续)比如:字符串为addca...

【题解】电缆线(2019青岛市程序设计竞赛)

【问题描述】在郊区有N座通信基站,P条双向电缆,第 i 条电缆连接基站 A_i 和 B_i。特别地,1号基站是通信公司的总站,N号基站位于一座农场中。现在,农场主希望对通信线路进行升级,其中升级第 i...