💡题解思路

✅ 目标：

最小化木板数量，使得所有泥坑的区间 $[s_i, e_i)$ 全部被覆盖，每块木板长度为固定的 $L$。

✅ 处理流程：

将所有泥坑按起点 $s_i$ 升序排序；

使用贪心策略，从当前未被覆盖的位置开始，每次尽量往后铺木板直到当前泥坑被完全覆盖；

用一个变量 cover_pos 表示当前已经覆盖到的最远位置。

✅ 算法步骤：

初始化答案 res = 0，覆盖位置 cover_pos = 0；

遍历所有泥坑 $[s_i, e_i)$：

如果 $cover_pos < s_i$，说明中间有空隙，直接从 $s_i$ 开始；

否则从 $\max(s_i, cover_pos)$ 开始往后铺；

计算当前泥坑剩余长度 $remain = e_i - cover_pos$；

所需木板数为 $\lceil \frac{remain}{L} \rceil$；

更新 cover_pos = cover_pos + count \times L，并将 count 累加到答案中。

✅ 样例解释

泥坑范围如下：

$[1,6)$：长度为 $5$，用两块木板；

$[8,12)$：长度为 $4$，用两块木板；

$[13,17)$：长度为 $4$，用一块木板；

合计需要 $5$ 块木板。

⌛时间复杂度

排序：$O(N \log N)$；

遍历每个泥坑：$O(N)$；

总体复杂度：$O(N \log N)$，适用于 $N \leq 10,!000$ 的数据范围。

代码实现

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list>  
using namespace std;  
const double eps = 1e-8;  
typedef long long LL;  
typedef unsigned long long ULL;  
const int INT_INF = 0x3f3f3f3f;  
const int INT_M_INF = 0x7f7f7f7f;  
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;  
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;  
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};  
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};  
const int MOD = 1e9 + 7;  
const double pi = acos(-1.0);  
const int MAXN = 1e5 + 10;  
const int MAXT = 10000 + 10;  
const int M=10005;
struct node
{
	int x,y;
};
bool cmp(const node &a,const node &b)
{
	if(a.x!=b.x)
		return a.x<b.x;
	else 
		return a.y<b.y;
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		node a[M];
		for(int i=0;i<n;i++)
		{
			scanf("%d%d",&a[i].x,&a[i].y);
		}
		sort(a,a+n,cmp);
		int p=0;
		int ans=0;
		for(int i=0;i<n;i++)
		{
			if(p>=a[i].y) continue;
			if(p<=a[i].x) {p=a[i].x;}    //注意和下面顺序不能错
			if(p<=a[i].y)
			{
				if((a[i].y-p)%m==0)
				{
					ans+=(a[i].y-p)/m;
					p=a[i].y;
				}
				else	
				{
					ans+=(a[i].y-p)/m+1;
					p+=((a[i].y-p)/m+1)*m ;
				}
				
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}