P5145: 超级弹簧

---

【题目描述】

题目描述

小明收到了一份特别的生日礼物，n 根可以伸缩的弹簧。现在把它们摆放到一条水平数轴上，其中每根弹簧摆放的左、右端点均为正整数，且在[1,m]之间。假设超级弹簧可拉伸至无限长，但要遵守这样的拉伸规则，即每次拉伸操作，弹簧只能向左、向右同时延长1个单位，即弹簧从区间[L,R]，拉长至区间[L-1,R+1] 。
请问若想区间 [1,m]中每一个整数点（包括两端点），至少被一根弹簧覆盖，那么最少的操作次数是多少？

输入描述

输入数据第一行，两个正整数n、m，依次表示n根弹簧，要覆盖的区间[1,m]的右端点m。
接下来n行，每行包含两个正整数L、R，依次表示每根弹簧摆放的左端点、右端点。

输出描述

输出数据一行，一个整数，表示符合要求的最少操作次数。

样例1

输入
3 10
6 8
2 4
9 9
输出
2

提示

测试点1和2 ：1≤n,m≤10,1≤L≤R≤m;
测试点3，4和5：1≤n,m≤200,1≤L≤R≤m;
测试点6，7，8，9和10：1≤n,m≤3000,1≤L≤R≤m.

【输入】

输入数据第一行，两个正整数n、m，依次表示n根弹簧，要覆盖的区间[1,m]的右端点m。

接下来n行，每行包含两个正整数L、R，依次表示每根弹簧摆放的左端点、右端点。

【输出】

输出数据一行，一个整数，表示符合要求的最少操作次数。

【提示】

测试点1和2 ：1≤n,m≤10,1≤L≤R≤m;

测试点3，4和5：1≤n,m≤200,1≤L≤R≤m;

测试点6，7，8，9和10：1≤n,m≤3000,1≤L≤R≤m.

题目类型~

海淀区第五届“智慧杯”中小学生计算机程序设计大赛普及组 

咻咻~

提交答案 状态 返回